题目描述
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。
输出
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
样例输入
5 4 PHPP PPHH PPPP PHPP PHHP
样例输出
6
题解
设dp[ i ][ j ][ k ] 表示 在第 i 行，状态为 j ，上一行状态为 k 的最大方案数。还是老套路，搞一搞就行了。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=100+5; const int maxm=(1<<10); int n,m,top,state[maxm],dp[2][maxm][maxm]; int cur[maxm],ans,w=1; char c; bool ok(int x){ if(x&(x<<1)) return false; if(x&(x<<2)) return false; return true; } void init(){ for(int i=0;i<(1<<m);i++) if(ok(i)) state[++top]=i; } bool fit(int x,int k){ if(x&cur[k]) return false; return true; } bool pd(int x,int y){ if(state[x]&state[y]) return false; return true; } int count(int x){ int ret=0; while(x){ ret++; x&=x-1; } return ret; } template<typename T>void read(T& aa){ char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); aa*=ff; } int main(){ read(n),read(m); for(int i=1;i<=n;i++){ cur[i]=0; for(int j=1;j<=m;j++){ cin>>c; if(c=='H') cur[i]+=(1<<m-j); } } init(); for(int i=1;i<=top;i++) if(fit(state[i],1)) dp[1][i][0]=count(state[i]); for(int i=1;i<=top;i++){ if(!fit(state[i],2)) continue; int tot=count(state[i]); for(int k=1;k<=top;k++){ if(!fit(state[k],1)) continue; if(!pd(i,k)) continue; dp[0][i][k]=max(dp[0][i][k],dp[1][k][0]+tot); } } for(int i=3;i<=n;i++,w^=1) for(int j=1;j<=top;j++){ if(!fit(state[j],i)) continue; int tot=count(state[j]); for(int k=1;k<=top;k++){ if(!fit(state[k],i-1)) continue; if(!pd(j,k)) continue; for(int t=1;t<=top;t++){ if(!fit(state[t],i-2)) continue; if(!pd(j,t)||!pd(t,k)) continue; dp[w][j][k]=max(dp[w][j][k],dp[w^1][k][t]+tot); } } } for(int i=1;i<=top;i++){ if(!fit(state[i],n)) continue; for(int j=1;j<=top;j++){ if(!fit(state[j],n-1)) continue; if(!pd(i,j)) continue; ans=max(ans,dp[w^1][i][j]); } } cout<<ans; return 0; }