洛谷 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;
- }
来源: http://www.bubuko.com/infodetail-2813988.html