本文主要是介绍rqnoj328NOI 炮兵阵地，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），
也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；
一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
作为一个垃圾NOIP狗看见NOI题还是比较虚，又是状压dp，一开始完全是做都不敢做。
首先我们来分析这一道题的状态，由于这一步的转移牵扯到了上一步和上上一步，那么状态里至少会有两维表示上一步和上上一步。
题目最难的如何设计可转移的状态，上下各两格没有其他的士兵。看了题解才发现了一个非常精妙的操作，用一个2进数表示每个点有没有士兵，0表示有，1表示没有，那么这个数左移一位对这个数进行与操作的值不为0的话，则说明有一位左边一格是有兵的，同理左移两位对这个数进行与操作的值不为0的话，则说明有一位左边两格是有兵的，这样就处理出了在一条横线上的可行状态。对于一条竖线的话，直接进行与操作，有值则为不能放的。
在此还有一个问题就是如果快速判断是否是山丘。在处理的时候我们也将地形用2进制数表示，如果是山丘则为1。那么我们这时对于一个放兵的状态和这一行的地形进行与操作，那么如果有值则说明了这一位有兵在山丘上了，则不合法。
接着我们来考虑转移，根据之前分析的状态，我们可以用dp[i][sh][zhe]表示考虑到前i个，我们现在这个的状态是zhe，上一个状态为sh时的最大兵数。那么它便可以从合法的dp[i-1][ss][sh]表示考虑到前i-1个，我们现在这个的状态是sh，上一个状态为ss时的最大兵数转移而来。
最后答案就是所有考虑到最后一行里的可行解转移而来。
不过最后要注意一个细节，对于第一行，它是没有上一个状态的，所以需要将它的这一个状态直接初始化为这一行的兵数。
下附AC代码。
#include<iostream>
#include<string.h>
#define maxn 105
using namespace std;
int n,m;
int cnt;
int g[maxn];
int state[maxn];
int sum[(1<<11)];
int dp[maxn][maxn][maxn];
int cal(int s)
{int ans=0;for(int i=0;i<m;i++){if(((s>>i)&1))ans++;}return ans;
}
bool check(int s)
{if((s&(s<<1))) return false;if((s&(s<<2))) return false;return true;
}
void findstate()
{for(int i=0;i<(1<<m);i++)if(check(i)){state[cnt++]=i;sum[i]=cal(i);}
}int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){char a;cin>>a;if(a=='H'){g[i]|=(1<<j);}}}findstate();memset(dp,-1,sizeof(dp));for(int i=0;i<cnt;i++)if((g[0]&state[i])==0){dp[0][0][i]=sum[state[i]];}int ans=0;for(int i=1;i<n;i++){for(int zhe=0;zhe<cnt;zhe++){if(g[i]&state[zhe]) continue;for(int sh=0;sh<cnt;sh++){if( (state[zhe]&state[sh] )|| (g[i-1]&state[sh]) ) continue;for(int ss=0;ss<cnt;ss++){if(state[zhe]&state[ss]) continue;if(state[sh]&state[ss]) continue;if(state[ss]&g[i-2]) continue;if(dp[i-1][ss][sh]==-1) continue;dp[i][sh][zhe]=max(dp[i][sh][zhe],dp[i-1][ss][sh]+sum[state[zhe]]);}}}}for(int i=0;i<cnt;i++)for(int j=0;j<cnt;j++){ans=max(ans,dp[n-1][i][j]);}cout<<ans<<endl;
} 这篇关于rqnoj328NOI 炮兵阵地的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
