AcWing 292. 炮兵阵地
原题链接
中等
作者:
微笑
,
2019-10-07 16:52:36
,
所有人可见
,
阅读 1490
每个状态可以影响到往下两层,所以要枚举当前行状态,上一行状态以及上上行的状态,同样,记录的时候也要再加一维,dp[i][j][k]表示,放好前i行,第i行状态为j,第i-1行状态为k的时候,能放置的最大数量,因为求的是最多的放置数量,也就需要求每个状态1的个数,所以也需要预处理出每个状态对应的1的数量。
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int dp[110][100][100],num[105],tem[105],top;
int mp[110];
int get(int x)
{
int ans=0;
while(x)
{
if(x&1) ans++;
x>>=1;
}
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
string s;
int sum=0;
cin>>s;
for(int j=0;j<m;j++)
if(s[j]=='P') sum+=1<<(m-j-1); //构建地图,1是能放置,0是不能放
mp[i]=sum;
}
for(int i=0;i<(1<<m);i++)
{
if(i&(i<<1) || i&(i<<2)) continue; //比之前的题多了一个距离
tem[top]=i;num[top++]=get(i);
}
for(int i=0;i<top;i++) //因为枚举的时候要往上枚举两行,所以要处理出第一行的值,第一行不需要考虑与上面冲突
if((mp[1]|tem[i])==mp[1]) dp[1][i][0]=num[i];
for(int i=2;i<=n;i++)
for(int j=0;j<top;j++)
{
if((tem[j]|mp[i])!=mp[i]) continue; //只能在地图上为1的地方放置
for(int k=0;k<top;k++)
{
if(tem[k]&tem[j]) continue //与上一行冲突
for(int r=0;r<top;r++)
{
if(tem[r]&tem[j] || tem[k]&tem[r]) continue; //与上上行冲突或者前两行互相冲突
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][r]+num[j]); //取max
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<top;j++)
for(int k=0;k<top;k++)
ans=max(ans,dp[i][j][k]); //注意要遍历所有状态,求出最大值
cout<<ans<<endl;
return 0;
}
xx
真的很厉害