题解 | #炮兵阵地#
炮兵阵地
https://ac.nowcoder.com/acm/problem/16886
本题算是[SCOI2005]互不侵犯KING (nowcoder.com)这道题的升级版，在互不侵犯这道题里面除了同一行的限制，上下行的限制仅仅包含一行。而在这道题里面则是包含了两行。
那么我们可以像互不侵犯那样将状态转移数组设成dp[i][j]，i表示某一层，j表示当前层的二进制数吗？当然不行，因为就算在遍历的时候去判断当前和上一个以及上上个是否符合要求那他们的值也不具有相加性。
所以在这里我们将两层间的状态也一起维护了，状态转移数组设置成：dp[i][j][k]。i表示某一层，j表示当前层的二进制数，k表示上一层的二进制数。这样将两层间捆绑就可以将其值相加了。
还这题中除了简单地处理不能相邻的问题外，还需要判断地形带来的影响。之间暴力的去判断肯定不行，在这里我们观察到地形其实也只有可以与不可以两种，所以果断就是一手二进制处理。
将其可以放的地方变成0，不可放地方变成1，那么如果全部放置正确的话他们按位与运算的结果必然是0，如果有一个不正确就大于0。
然后状态转移方程：dp[i][cur][upp1] = max(dp[i][cur][upp1], dp[i-1][upp1][upp2]+p[cur].second);
#include <bits/stdc++.h>
using namespace std;
int n, m;
int cnt = 0;
pair<int, int> p[1<<10];
int mp[110];
int dp[110][1<<10][1<<10];
int num(int i) {
int ans = 0;
while (i) {
if (i&1) {
ans++;
}
i = (i>>1);
}
return ans;
}
int main() {
cin>>n>>m;
for (int i=0;i<(1<<m);i++)
{
if (((i<<1)&i)==0&&((i<<2)&i)==0) {
p[cnt++] = make_pair(i, num(i));
}
}
char ch;
for (int i=1;i<=n;i++) {
int num = 0;
for (int j=m-1;j>=0;j--) {
cin>>ch;
if (ch=='H') {
num = num|(1<<j);
}
}
mp[i] = num;
// cout<<"num="<<num<<endl;
}
int ans = 0;
for (int i=1;i<=n;i++)
{
for (int cur=0;cur<cnt;cur++)
{
if (mp[i]&p[cur].first) continue;
for (int upp1=0;upp1<cnt;upp1++)
{
if (p[cur].first&p[upp1].first) continue;
for (int upp2=0;upp2<cnt;upp2++)
{
if (p[cur].first&p[upp2].first) continue;
if (p[upp1].first&p[upp2].first) continue;
dp[i][cur][upp1] = max(dp[i][cur][upp1], dp[i-1][upp1][upp2]+p[cur].second);
ans = max(ans, dp[i][cur][upp1]);
}
}
}
}
cout<<ans;
return 0;
}
投递阅文集团等公司7个岗位 >