这道题看数据范围n<=10可以很快的想出是状压DP。
之后最暴力的方法也是可以想到的，就是直接暴力枚举当前行，上一行，上上行的情况（因为炮兵能打两行），直接暴力DP。
不过这样一来会T，二来会MLE。
那我们怎么办？我们注意到一个炮兵能打到左右两格，说明在一行之内有很多情况都是不可行的，根本不用枚举。我们可以直接先行预处理出所有可行的情况，方法就是暴力枚举1~1<<m-1，对于每个i，判断其&i<<2,i<<1,i>>1,i>>2即可。（这个在互不侵犯那道题中都是老套操作了）
这样就处理出了每行所有可行的情况，我们惊奇的发现其实最多有60种……
之后就可以像刚才一样暴力的状压DP了。
只要预处理之后，记录一下每行的地形，继续用按位与的方法判断当前情况是否可行，之后求解即可。然后，注意在判断三行的情况的时候要分别判断每个两行是否可行，一起判断由于中间按位与可能为0，会出现错误。
注意第一行和第二行要单独处理。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> //#include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 205; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,m,shape[105],s[205],dp[105][205][205],sum[205],k,ans; char g[105][15]; int getsum(int x) { int cur = 0; while(x) { cur += (x&1); x >>= 1; } return cur; } void init1() { rep(i,0,(1<<m)-1) { if((!(i&(i<<1))) && (!(i&(i<<2))) && (!(i&(i>>1))) && (!(i&(i>>2)))) { s[++k] = i; sum[k] = getsum(i); if(!(i&shape[1])) dp[1][0][k] = sum[k]; } } } void init2() { rep(i,1,k) rep(j,1,k) { if((!(s[i]&s[j])) && (!(s[j]&shape[2]))) dp[2][i][j] = max(dp[2][i][j],dp[1][0][i] + sum[j]); } } int main() { n = read(),m = read(); rep(i,1,n) { scanf("%s",g[i]); rep(j,0,m-1) if(g[i][j] == 'H') shape[i] |= (1 << j); } init1(),init2(); rep(i,3,n) rep(j,1,k) { if(!(s[j] & shape[i])) { rep(p,1,k) { if(!(s[j] & s[p])) rep(q,1,k) { if((!(s[q] & s[p])) && (!(s[q] & s[j]))) dp[i][p][j] = max(dp[i][p][j],dp[i-1][q][p] + sum[j]); } } } } rep(i,1,k) rep(j,1,k) ans = max(ans,dp[n][i][j]); printf("%d ",ans); return 0; }