<算法进阶指南>题解补全计划—进阶指北
此篇属于
算法进阶指南题解补全计划—进阶指北收录题解
:传送门
代码不仅要写的正确,而且还要写的优雅。
这一题与上一题
蒙德里安的梦想【题解传送门】
类似,不过在状态转移上面有一点区别。
可能爆空间,用滚动数组来做(因为当前状态只和上一层f相关)
笔记指北
code
#include<iostream>
#include<vector>
using namespace std;
const int N = 110, M = 1 << 10;
int n,m;
int g[N],cnt[M];
int f[2][M][M];
vector<int>state;
vector<int>head[M];
bool check(int st)
{
return (st & st >> 1 || st & st >> 2) ? 0 : 1;
}
int count(int st)
{
int res = 0;
while(st) res += st & 1,st >>= 1;
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1,j = 0;i <= n;i ++, j = 0)
for(char c;j < m && cin >> c;j ++)
g[i] += (c == 'H') << j;
for(int st = 0;st < 1 << m; st ++)
if(check(st)) state.push_back(st),cnt[st] = count(st);
for(int now_st:state)
for(int pre_st:state)
if(!(now_st & pre_st))
head[now_st].push_back(pre_st);
for(int i = 1;i <= n + 2;i ++)
for(int st:state)
if(!(g[i] & st))
for(int p1:head[st])
for(int p2:head[st])
if(!(st & p2))
f[i&1][st][p1] = max(f[i&1][st][p1],f[i-1&1][p1][p2] + cnt[st]);
cout << f[n + 2 & 1][0][0] << endl;
return 0;
}