题目大意：
一个n*m(n<=100,m<=10)的格子图，里面有些地方可以放炮兵，有些地方不行，炮兵能像上下左右攻击到两格远的位置。
问在炮兵不会互相攻击的情况下，最多能放多少炮兵？
思路：
状压DP。
f[i][j][k]表示DP到第i行，当前行状态为j，上一行状态为k。
然后枚举当前行，这一行状态，上一行状态和上两行状态，判断是否合法并转移即可。
复杂度很悬，然而洛谷和百练上随便A，但是POJ确实过不去。
考虑横向互相攻击的情况，这对每一行都是一样的，而且似乎无效状态会有很多。
那我们就预处理出同一行中所有的合法情况，极限情况下不会超过60个。
这样枚举的时候就能节约不少时间。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<algorithm> 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^‘0‘; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 10 return x; 11 } 12 const int N=100,M=10; 13 int a[N]; 14 int f[2][1<<M][1<<M]; 15 int sit[61]; 16 int main() { 17 int n=getint(),m=getint(); 18 for(register int i=0;i<n;i++) { 19 for(register int j=0;j<m;j++) { 20 char c[2]; 21 scanf("%1s",c); 22 if(*c==‘H‘) a[i]|=1<<j; 23 } 24 } 25 for(register int i=0;i<(1<<m);i++) { 26 for(register int t=2;t<m;t++) { 27 if(((i>>t)&(i>>(t-1)))||((i>>(t-1))&(i>>(t-2)))||((i>>t)&(i>>(t-2)))) goto Next; 28 } 29 sit[++sit[0]]=i; 30 Next:; 31 } 32 for(register int j=1;j<=sit[0];j++) { 33 if(sit[j]&a[0]) continue; 34 f[0][sit[j]][0]=__builtin_popcount(sit[j]); 35 } 36 for(register int j=1;j<=sit[0];j++) { 37 if(sit[j]&a[1]) continue; 38 for(register int k=1;k<=sit[0];k++) { 39 if(sit[k]&(sit[j]|a[0])) continue; 40 f[1][sit[j]][sit[k]]=std::max(f[1][sit[j]][sit[k]],f[0][sit[k]][0]+__builtin_popcount(sit[j])); 41 } 42 } 43 for(register int i=2;i<n;i++) { 44 memset(f[i&1],0,sizeof f[i&1]); 45 for(register int j=1;j<=sit[0];j++) { 46 if(sit[j]&a[i]) continue; 47 for(register int k=1;k<=sit[0];k++) { 48 if(sit[k]&(sit[j]|a[i-1])) continue; 49 for(register int l=1;l<=sit[0];l++) { 50 if(sit[l]&(sit[j]|sit[k]|a[i-2])) continue; 51 f[i&1][sit[j]][sit[k]]=std::max(f[i&1][sit[j]][sit[k]],f[!(i&1)][sit[k]][sit[l]]+__builtin_popcount(sit[j])); 52 } 53 } 54 } 55 } 56 int ans=0; 57 for(register int i=1;i<=sit[0];i++) { 58 for(register int j=1;j<=sit[0];j++) { 59 ans=std::max(ans,f[!(n&1)][sit[i]][sit[j]]); 60 } 61 } 62 printf("%d\n",ans); 63 return 0; 64 }
原文：http://www.cnblogs.com/skylee03/p/7745869.html