『状态压缩DP』炮兵阵地

题目描述

题解

这道题真的毒瘤…

首先观察到列的范围很小，这启示我们使用状态压缩算法。

我们可以预处理出所有横排不互相攻击的数字，显然这些数只有一百来个。用b数组存储。

我们观察到一行是否可以防止炮兵和上两行来决定，我们设$f[i][j][k]$表示第$i$行的状态为$b_j$，第$i?1$行状态为$b_k$可以放置的最多炮兵。

因此我们设令一个状态为l，有一个显然的状态转移方程是：$$f[i][j][k]=max(f[i][j][k],f[i?1][k][l]+count(j))$$
此时，我们需要考虑这个状态转移方程的限制条件：

• 显然，为了防止互相攻击，必须要满足第$b[i]\&b[i?1]=?0$和$b[i]\&b[i?2]=?0$.
• 为了让都在平原上，需满足$a[i]|p=a[i]$. p ∈ { j , k } . p∈\{j,k\}. p∈{ j,k}.
• 然后我们让$f[0][1][1]=0$(若$b[1]=0$),其余为负无穷。还有，$count(i)$表示数字i的二进制1的个数。

代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 200;int n, m, ans = 0, s = 0;
int a[N], f[N][N][N], b[N], c[N];bool check(int x)
{
    int t[20] = {
    };for (int i=m-1;i>=0;--i) t[i+1] = x >> i & 1;for (int i=3;i<=m;++i) if (t[i]+t[i-1]+t[i-2] > 1) return 0;return 1;
}bool valid(int x,int y) {
    return (x | a[y]) == a[y];
}bool safe(int x,int y,int z) {
    return (b[x] & b[y]) == 0 && (b[y] & b[z]) == 0 && (b[x] &b[z]) == 0;
}int count(int x) {
    int cnt = 0;while (x > 0) cnt += x&1, x >>= 1;return cnt;
}int main(void)
{
    freopen("input.in","r",stdin);freopen("output.out","w",stdout);cin >> n >> m;for (int i=1;i<=n;++i){
    int s = 0;for (int j=1;j<=m;++j){
    char c;cin >> c;if (c == 'P') s = s<<1|1;else s = s<<1;}a[i] = s;}for (int i=0;i<1<<m;++i) if (check(i)) b[++s] = i, c[s] = count(i);memset(f,-30,sizeof f);f[0][1][1] = 0;for (int i=1;i<=n;++i)for (int j=1;j<=s;++j) if (valid(b[j],i))for (int k=1;k<=s;++k) if (valid(b[k],i-1) && (b[j]&b[k]) == 0)for (int l=1;l<=s;++l) if ((b[j]&b[l]) == 0) f[i][j][k] = max(f[i][j][k],f[i-1][k][l]+c[j]), ans = max(ans,f[i][j][k]);cout << ans << endl;return 0;
}