求大佬查错!!谢谢大佬!!!

P2704 [NOI2001] 炮兵阵地

圣堂之地 @ 2019-08-29 20:48:38

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int M=105;

vector <int> v[M];//v[i]记录行数为i的所有状态 

int n,m,ans,vis[1025],sum[1025],a[M],dp[101][1005][1005];//a[i]压行 
//1为可以  0为不可以

inline int check(int s){return !(s&(s<<1))&&!(s&(s<<2))&&!(s&(s>>1))&&!(s&(s>>2));}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char tmp;
            cin>>tmp;
            if(tmp=='P') a[i]=(a[i]<<1)+1;
            else a[i]<<=1;
        }
    }

    for(int s=0;s<(1<<n);s++) //预处理 
        if(check(s)){
            if((a[1]&s)==s) v[1].push_back(s); //第一行 
            bitset <10000> tmp(s);
            sum[s]=tmp.count(); //计算1的个数 
            dp[1][0][s]=sum[s];//初始化 
            vis[s]=1;//这种状态在 不考虑平原山脉的情况 下可行 
        }

    for(int s1=0;s1<(1<<m);s1++){//第二行 
        for(int i=0;i<v[1].size();i++){
            int s2=v[1][i];//第一行状态为s1 
            if(!(s1&s2)&&vis[s1]&&vis[s2]&&(a[2]&s1)==s1) 
                v[2].push_back(s1),dp[2][s2][s1]=max(dp[2][s2][s1],dp[1][0][s2]+sum[s1]); 
        }//如该种状态可行,第二行加入此状态 
    }

    for(int i=3;i<=n;i++){
        for(int s=0;s<(1<<m);s++){//枚举当前状态 
            if(vis[s]&&(s&a[i])==s){
                for(int a=0;a<v[i-1].size();a++){//枚举上一行状态  
                    int s1=v[i-1][a];//上一行状态为s1 
                    for(int b=0;b<v[i-2].size();b++){//枚举上两行状态  
                        int s2=v[i-2][b];//上两行状态为s2 
                        if((!(s&s1))&&!(s&s2)&&!(s1&s2))//互相无法炮击 
                            v[i].push_back(s),dp[i][s1][s]=max(dp[i][s1][s],dp[i-1][s2][s1]+sum[s]); 
                    }//这一行加入该状态 
                }
            } 
        }
    }

    for(int a=0;a<v[n].size();a++){
        int s1=v[n][a];
        for(int b=0;b<v[n-1].size();b++){
            int s2=v[n-1][b];
            ans=max(ans,dp[n][s2][s1]);
        }
    } 

    printf("%d",ans);

    return 0;
}

|