三维的dp[i][a][b]，表示第i行，前一行状态为a，再前一行的状态为b，用二进制表是状态如10010表示第一和第四个位置有阵地，然后预处理出每一种状态的炮兵数量。
每一行读取完后就预处理该行所有可能的状态， x&x<<1和x&x<<2 的值为0即本行炮兵不会相互干扰（详见位运算）。
注意第一行和第二行先进行dp，再处理后面几行。
#include<cstdio> #include<cstring> #include<algorithm> #define N 10 using namespace std; int z, st[111], s[111][1<<N],//枚举每行所有可能的状态 num[1<<N]//每种状态炮兵数量, dp[111][1<<N][1<<N]; inline int pd(int x){ return x&(x<<1)||x&(x<<2); } inline int pd2(int x, int y){ return x&y; } void turn(){ for(int i=0;i<z;i++){ int x=i, sum=0; while(x){ sum+=x&1; x>>=1; } num[i]=sum; } } int main() { int n, m; char c[20]; scanf("%d %d", &n, &m); z=1<<m; for(int i=1;i<=n;i++){ scanf("%s", c); for(int j=0;j<m;j++){ if(c[j]=='H') st[i]+=(1<<j); } for(int k=0;k<z;k++) if(!pd(k)&&!pd2(k,st[i])) s[i][++s[i][0]]=k; } turn(); for(int i=1;i<=s[1][0];i++) dp[1][s[1][i]][0]=num[s[1][i]]; for(int i=1;i<=s[2][0];i++){ for(int j=1;j<=s[1][0];j++){ if(pd2(s[2][i],s[1][j])) continue; dp[2][s[2][i]][s[1][j]]=max(dp[2][s[2][i]][s[1][j]], dp[1][s[1][j]][0]+num[s[2][i]]); } } for(int i=3;i<=n;i++) for(int a=1;a<=s[i][0];a++){ for(int b=1;b<=s[i-1][0];b++){ if(pd2(s[i][a],s[i-1][b])) continue; for(int c=1;c<=s[i-2][0];c++){ if(pd2(s[i][a],s[i-2][c])) continue; dp[i][s[i][a]][s[i-1][b]]=max(dp[i][s[i][a]][s[i-1][b]], dp[i-1][s[i-1][b]][s[i-2][c]]+num[s[i][a]]); } } } int maxn=0; for(int i=1;i<=s[n][0];i++) for(int j=1;j<=s[n-1][0];j++) maxn=max(maxn,dp[n][s[n][i]][s[n-1][j]]); printf("%d\n", maxn); return 0; }