【题解】洛谷P2704 [NOI2001] 炮兵阵地（状压DP）

洛谷P2704：https://www.luogu.org/problemnew/show/P2704

思路

这道题一开始以为是什么基于状压的高端算法

没想到只是一道加了一行状态判断的状压DP而已

与普通状压并无多大区别

详细见代码

代码

#include<iostream> using namespace std; #define maxn 1010 int f[110][maxn][maxn],num[maxn],st[maxn],map[110]; int n,m,ans,state; int get(int x)//计算每行1的个数 { int t=0; while(x>0) { ++t; x-=x&(-x);//减去lowbit 就是最后一个1 } return t; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char x; cin>>x; if(x=='H')//如果是山地就是1 map[i]=(map[i]<<1)+1; if(x=='P')//如果是平原就是0 map[i]=(map[i]<<1); } for(int i=0;i<=(1<<m)-1;i++)//枚举所有状态查找可用状态 if(!(i&(i<<1))&&!(i&(i<<2))&&!(i&(i>>1))&&!(i&(i>>2)))//判断此行可用 { st[++state]=i;//记录状态 num[state]=get(i);//计算1的个数 if(!(i&map[1])) f[1][0][state]=num[state];//初始化第一行 如果不与地形冲突 } for(int i=1;i<=state;i++)//初始化第二行 for(int j=1;j<=state;j++) if(!(st[i]&st[j])&&!(st[j]&map[2])) //如果第二行和第一行和地形都不冲突 f[2][i][j]=max(f[2][i][j],f[1][0][i]+num[j]); for(int i=3;i<=n;i++)//从第三行开始枚举 for(int j=1;j<=state;j++)//枚举此行状态 if(!(map[i]&st[j]))//判断是否和地形冲突 { for(int k=1;k<=state;k++)//枚举上一行状态 if(!(st[j]&st[k]))//上一行不与此行冲突 { for(int t=1;t<=state;t++)//枚举上上行状态 if(!(st[t]&st[k])&&!(st[t]&st[j]))//上上行不与上一行和此行冲突 f[i][k][j]=max(f[i][k][j],f[i-1][t][k]+num[j]);//记录 } } for(int i=1;i<=state;i++)//枚举最后两行的所有状态 for(int j=1;j<=state;j++) ans=max(ans,f[n][i][j]);//取最大值 cout<<ans; }

 

转载于:https://www.cnblogs.com/BrokenString/p/9818443.html

相关资源：JAVA上百实例源码以及开源项目