题解 P2704 【炮兵阵地】

本文主要是介绍题解 P2704 【炮兵阵地】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题和P1879 [USACO06NOV]玉米田Corn Fields有类似的地方，但这道题可以看为那道题的升级版，所以我建议没做过玉米田的可以先做一下玉米田和P1896 [SCOI2005]互不侵犯King。

1.

解此题的关键在于要知道第i行的状态是由前两行的状态决定的，所以要预处理出第一行和第二行的所有状态，然后从第三行（因为第一二行已处理）开始枚举，同时枚举第当前行的前一行和上上行。

2.

同时还需注意预处理时应把每种情况所能放置炮兵数求出来：

for(int i=0;i<(1<<m);i++)if(!(i&(i<<2))&&!(i&(i<<1))){sit[++k]=i;int t=i;while(t){sum[k]+=t%2;t/=2;}}

3.

（1）dp方程是什么呢？

f[i][l][j]=max(f[i][l][j],f[i-1][p][l]+sum[j]);（这里大家要深刻理解f[i][l][j]的含义，千万不要把顺序弄反）

f[i][l][j]的意思是第i行的j状态是由上一行的l状态得出来的。

（2）为什么要求max呢？

首先先不论正确性，交上去会wa5个点，实际值都比答案小；其次这道题和玉米田不同的是此题求的是最多炮兵数（是最优性问题求解），而玉米田问的是总方案数，这是有很大区别的；然后既然是是最优性问题求解，那么肯定要从前两行的所有状态中求出使当前行状态最优的状态，满足阶段最优和无后效性原则。

4.

最后从最后一行（即最终状态）中找出最优状态，这就是解。

5.代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[105][500][500],sit[5000],n,k=0,ans=-1,m,map[5000],sum[5000];
int main()
{scanf("%lld %lld",&n,&m);for(int i=1;i<=n;i++){scanf("\n");for(int j=1;j<=m;j++){char s;map[i]=map[i]<<1;scanf("%c",&s);if(s=='H')map[i]=map[i]|1;//这里要让H为1，P为0，这样方便储存状态； }}for(int i=0;i<(1<<m);i++)//处理炮兵放置方案（情况） if(!(i&(i<<2))&&!(i&(i<<1))){sit[++k]=i; //放置方案 int t=i;while(t){sum[k]+=t%2;//当前状态放置炮兵数量 t/=2;}}for(int i=1;i<=k;i++)if(!(sit[i]&map[1]))f[1][1][i]=sum[i];//处理第一行的状态 //下面一个for是处理第二行的状态  for(int i=1;i<=k;i++)//枚举第二行所有炮兵放置情况 if(!(sit[i]&map[2]))for(int j=1;j<=k;j++)//枚举第一行…… {if(!(map[1]&sit[j])&&!(sit[i]&sit[j]))f[2][j][i]=sum[i]+sum[j];}for(int i=3;i<=n;i++)for(int j=1;j<=k;j++)//枚举当前行…… if(!(map[i]&sit[j]))for(int l=1;l<=k;l++)//枚举上一行…… if(!(sit[j]&sit[l])&&!(map[i-1]&sit[l]))for(int p=1;p<=k;p++)//枚举上上行…… if(!(sit[p]&sit[l])&&!(map[i-2]&sit[p])&&!(sit[p]&sit[j]))f[i][l][j]=max(f[i][l][j],f[i-1][p][l]+sum[j]);for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)ans=max(f[n][j][i],ans);//处理答案 printf("%lld",ans);
}