滚动数组求调试,谢谢

P2704 [NOI2001] 炮兵阵地

lyxleo @ 2022-10-27 14:27:34

这个代码没过样例,我挑不出来,故求大佬调试,谢谢

#include <iostream>
#include <string.h>
using namespace std;
unsigned int n,m;
unsigned int state[105];//表示每一行的空地 
unsigned int dp[3][1 << 11][1 << 11];
unsigned int ones[1 << 11];
inline bool check(const int &i){
    return ((i & (i << 1)) == 0 && (i & (i << 2)) == 0);
}
int main(){
    cin>>n>>m;
    for(unsigned int i = 0;i < (1 << m);++i){
        unsigned int s = 0;
        for(unsigned int j = i;j;j -= (j & (-j))) ++s;
        ones[i] = s;
    }
    for(unsigned int i = 0;i < n;++i){
        for(unsigned int j = 0;j < m;++j){
            char c;
            cin>>c;
            if(c == 'P'){
                state[i] += (1 << j);
            }
        }
    }

    for(unsigned int j = 0;j < (1 << m);++j){
        if((j & state[0]) == j && check(j)){
            for(unsigned int k = 0;k < (1 << m);++k){
                dp[0][j][k] = ones[j];
            }
        }
    }
    if(n == 1){
        unsigned int ans = 0;
        for(unsigned int j = 0;j < (1 << m);++j){
            if((j & state[0]) == j && check(j)){
                for(unsigned int k = 0;k < (1 << m);++k){
                    ans = max(ans,dp[0][j][k]);
                }
            }
        }
        cout<<ans;
        return 0;
    }
    for(unsigned int j = 0;j < (1 << m);++j){
        if((j & state[1]) == j && check(j)){
            for(unsigned int k = 0;k < (1 << m);++k){
                if((k & state[0]) == k && (j & k) == 0 && check(k)){
                    dp[1][j][k] = ones[j] + ones[k];
                }
            }
        }
    }

    for(int line = 2;line < n;++line){
        int i = line % 3;
        for(int j = 0;j < (1 << m);++j){
            if((j & state[line]) == j && check(j)){
                for(int k = 0;k < (1 << m);++k){
                    if(((k & state[line]) == k) && ((j & k) == 0) && check(k)){
                        for(int g = 0;g < (1 << m);++g){
                            if((g & state[line]) == g && check(g) && (g & j) == 0 && (g & k) == 0){
                                dp[i][j][k] = max(dp[i][j][k],dp[((i - 1) % 3 + 3) % 3][k][g] + ones[j]);
                            }
                        }
                    }
                }
            }
        }
    }

    unsigned int ans = 0;

    for(int i = 0;i < (1 << m);++i){
        if((i & state[n - 1]) == i && check(i)){
            for(int j = 0;j < (1 << m);++j){
                if((j & state[n - 2]) == j && check(j) && (i & j) == 0){
                    ans = max(ans,dp[(((n - 1) % 3) + 3) % 3][i][j]);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

|