题目链接:https://www.luogu.org/problem/P2704
蓝书状压DP例题。
读入时把山全部改为1,平地0。
还是先考虑预处理。
把所有单行合法的点记录下来,也就是1的左右两格都是0。
设f[i][j][k],表示在i行从i-1的j转移到k的最多的炮兵数。
那么肯定j和k所代表的状态按位与为0,j和k和原图的按位与也为0。
代码如下:
#include<cstdio> #include<algorithm> using namespace std; int n,m; int tu[110],g[1100],s[1100]; int f[110][1100][1100]; inline int count(int x){ int ans=0; for(;x;x-=(x&-x)) ans++; return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ char a[20];scanf("%s",a); for(int j=0;j<m;j++) if(a[j]=='H') tu[i]+=(1<<j); } int k=0; for(int i=0;i<(1<<m);i++) if( ((i&(i<<1))==0 ) && ((i&(i<<2))==0) && ((i&(i>>1))==0) && ((i&(i>>2))==0) ) { k++; s[k]=i; g[k]=count(i); if((i&tu[1])==0) f[1][0][k]=g[k]; } for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) if( ((s[i]&s[j])==0) && ((s[j]&tu[2])==0) ) f[2][i][j]=max(f[2][i][j],f[1][0][i]+g[j]); for(int i=3;i<=n;i++) for(int j=1;j<=k;j++) if((tu[i]&s[j])==0) for(int t=1;t<=k;t++) if((s[t]&s[j])==0) for(int z=1;z<=k;z++) if( ((s[t]&s[z])==0) && ((s[z]&s[j])==0) ) f[i][t][j]=max(f[i][t][j],f[i-1][z][t]+g[j]); int ans=0; for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) ans=max(ans,f[n][i][j]); printf("%d ",ans); return 0; }