题目：http://poj.org/problem?id=1185
大神的题解：
方法就是用DP[i][r][p]表示第i行状态为r，第i-1行状态是p时的最多个数。而这里p受到r的限制，而第i-2行状态q则受到r和p两个状态限制。状态转移方程就是：
DP[i][r][p] = MAX{DP[i-1][p][q] +num[r]}
其中，p是受到r的限制时枚举的状态，q是受到r和p共同限制时候的状态，num[r]表示状态r里面的布局炮兵所摆的个数。
这里我们可以看到就要枚举i，r，p，q,这4 个变量，i的范围是100，而其他几个则都是1<<10,复杂度颇为偏高。而实际上由于每一行里面有很多都是某些位置被其他位置影响的。比如： 1110001， 如果第一个位置放上炮兵，那么第二第三的位置都会受到影响，而一个也放不了。
解决方案就是不去管那些相互有影响的状态，把形如：
1000000 0100000 ... ...
1001000 0100001 ... ...
...
1001001
这些相互之间没有影响的状态找出来，这样所有的状态数就会减少至少于60种（我算了一下，好像是58种），这样一来就是60*60*60*100，可以过了。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #define mod 100000000 using namespace std; int m,n,top,state[110],cur[110],num[110],dp[110][110][110]; char tu[110][20]; inline bool ok(int x) { if(x&(x<<1)) return false; if(x&(x<<2)) return false; return true; } inline void init() { int tol=1<<n; top=0; for(int i=0; i<tol; i++) { if(ok(i)) state[++top]=i; } } inline bool fit(int x,int k) { if(x&cur[k]) return false; return true; } inline int icount(int x) { int cnt=0; while(x) { cnt++; x=x&(x-1); } return cnt; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { init(); for(int i=1; i<=m; i++) scanf("%s",tu[i]+1); for(int i=1;i<=m;i++) { cur[i]=0; for(int j=1;j<=n;j++) { if(tu[i][j]==‘H‘) cur[i]+=(1<<(n-j)); } } memset(dp,0,sizeof(dp)); for(int i=1; i<=top; i++) { num[i]=icount(state[i]); if(fit(state[i],1)) dp[1][1][i]=num[i]; } for(int i=2; i<=m; i++) { for(int t=1; t<=top; t++) { if(!fit(state[t],i)) continue;//符合本行 for(int j=1; j<=top; j++) { if(state[j]&state[t]) continue;//符合上一行 for(int k=1; k<=top; k++) //符合上上行 { if(state[k]&state[t]) continue; if(state[k]&state[j]) continue; dp[i][j][t]=max(dp[i][j][t],(dp[i-1][k][j]+num[t])); } } } } int maxx=-1; for(int i=1; i<=m; i++) { for(int j=1; j<=top; j++) { for(int k=1; k<=top; k++) { maxx=max(maxx,dp[i][j][k]); } } } printf("%d\n",maxx); } return 0; }
原文：http://www.cnblogs.com/zhangmingcheng/p/4372712.html