AcWing 292. 炮兵阵地(稍改附注释)
原题链接
中等
作者:
摸鱼喵
,
2021-01-06 20:00:50
,
所有人可见
,
阅读 849
配合Y总视频食用
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
const int N =110,M=1<<10;
int f[2][M][M];//代表前i行已经摆好,第i行的状态是j,第i-1行的状态是k.的最大值。
int n,m;
vector<int>state;//合法状态.
int g[N];//记录第i行的初始状态.
int cnt[M];//记录1的个数.
bool check(int u)//检查状态合法性
{
for(int i=0;i<m;i++)
if((u>>i&1)&&((u>>i+1&1)||(u>>i+2&1)))return false;
return true;
}
int count(int u)//计算数字中1的数量。
{
int res=0;
for(int i=0;i<=m;i++)res+=u>>i&1;
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int res=0;
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
if(c=='H')res+=1<<(m-j);
}
g[i]=res;
}
for(int i=0;i<1<<m;i++)//预处理合法状态.
{
if(check(i))
{
state.push_back(i);
cnt[i]=count(i);
}
}
//状态计算。
for (int i = 1; i <= n+2; i ++ )
for (int j = 0; j < state.size(); j ++ )
for (int k = 0; k < state.size(); k ++ )
for (int u = 0; u < state.size(); u ++ )
{
int a = state[j], b = state[k], c = state[u];//分别表示第i,i-1,i-2行的状态。
if (a & b || a & c || b & c) continue;//状态之间没有交集
if (g[i] & a ) continue;//检验该行的合法性,若某状态不合法值必定为0
f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]);
}
cout<<f[n+2&1][0][0]<<endl;
return 0;
}
自己的一些理解:
https://www.acwing.com/solution/content/239286/
一手好代码!