状态压缩的好题，直接求会爆内存，先把所有可能的状态求出来存在stk里，然后f[i][k][t]表示i行状态为t，i-1状态为k，由i-1状态来推出i状态即可
注意要打好边际条件的状态，并且某个可行状态必须由前一个可行状态推出
/* f[i][k][t]表示第i行状态为t，第i-1行状态为k的炮兵数 边际条件：第一行为任意可行状态即dp[1][1][i]=num[i] */ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 110 char a[maxn][maxn]; int stk[maxn],cur[maxn],num[maxn],f[maxn][maxn][maxn]; int n,m,top; inline bool legal(int x){//检查该状态是否会互相攻击 if(x&(x<<1))return false; if(x&(x<<2))return false; return true; } inline bool fit(int x,int k){//检查第k行在x状态下是否在山地上 if(x&cur[k])return false; return true; } inline void init(){//预处理，将合法的st存入stk中 top=0; for(int i=0;i<=(1<<m)-1;i++) if(legal(i))stk[++top]=i; } inline int jcount(int x){//计数 int cnt=0; while(x>0){cnt++;x&=(x-1);} return cnt; } int main(){ cin>>n>>m; init(); for(int i=1;i<=n;i++){ scanf("%s",a[i]+1); for(int j=1;j<=m;j++) if(a[i][j]=='H') cur[i]+=(1<<(m-j));//有山地的位置就是1 } memset(f,-1,sizeof f); for(int i=1;i<=top;i++){//预处理第一行 num[i]=jcount(stk[i]); if(fit(stk[i],1))f[1][1][i]=num[i];//如果这种状态可以放在第一行，那就摆下 for(int j=2;j<=top;j++)f[1][j][i]=0;//第二行开始炮兵数设置为0 } for(int i=2;i<=n;i++) for(int t=1;t<=top;t++){//枚举当前行的状态 if(!fit(stk[t],i))continue;//第i行不能放状态stk[t] for(int j=1;j<=top;j++){//枚举i-2行的状态 if(stk[t]&stk[j] || stk[j]&cur[i-2])continue; for(int k=1;k<=top;k++){ if(stk[t]&stk[k] || stk[j]&stk[k] || stk[k]&cur[i-1])continue; if(f[i-1][j][k]==-1)continue;//i-1行的这种状态不可达 f[i][k][t]=max(f[i][k][t],f[i-1][j][k]+num[t]); } } } int ans=0; for(int i=1;i<=top;i++) for(int j=1;j<=top;j++) ans=max(ans,f[n][i][j]); cout<<ans<<endl; }