萌新求助,#7,#9,#10 WA

P2704 [NOI2001] 炮兵阵地

啷里个浪 @ 2021-03-04 16:22:23

#include<bits/stdc++.h>
using namespace std;
int n,m,mapi[110],con[1<<11],js[1<<11],f[1<<11][1<<11][110],cnt;
int lowbiti(int x){
    int tot=0;
    while(x){
        if(x&1)++tot;
        x=x>>1;
    }
    return tot;
}
int main(){
    char ch;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch;
            mapi[i]=(mapi[i]<<1)+(ch=='H'?1:0);
        }
    }
    for(int i=0;i<(1<<m);i++){
        if((i&(i<<1))==0&&(i&(i<<2))==0&&(i&(i>>1))==0&&(i&(i>>2))==0){
            ++cnt;
            con[cnt]=i;
            js[cnt]=lowbiti(i);
        }
    }
    for(int i=1;i<=cnt;i++){
        if((mapi[1]&con[i])==0){
            f[0][i][1]=js[i];
        }
    }
    for(int i=1;i<=cnt;i++){
        if((mapi[2]&con[i])==0){
            for(int j=1;j<=cnt;j++){
                if((mapi[1]&mapi[j])==0&&(con[i]&con[j])==0)
                    f[j][i][2]=js[i]+js[j];
            }
        }
    }
    for(int i=3;i<=n;i++){//i
        for(int j=1;j<=cnt;j++){//the condition of i line
            if((mapi[i]&con[j])==0){
                for(int k=1;k<=cnt;k++){//the condition of i-1 line
                    if((mapi[i-1]&con[k])==0&&(con[j]&con[k])==0){
                        for(int l=1;l<=cnt;l++){//the condition of l-2 line
                            if((mapi[i-2]&con[l])==0&&(con[l]&con[k])==0&&(con[j]&con[l])==0)
                                f[k][j][i]=max(f[k][j][i],f[l][k][i-1]+js[j]);
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            ans=max(ans,f[i][j][n]);
        }
    }
    cout<<ans;
    return 0;
} 

|