洛谷P2704 [NOI2001] 炮兵阵地题解

题目链接：P2704 [NOI2001] 炮兵阵地

题意：

司令部的将军们打算在 \(N\times M\) 的网格地图上部署他们的炮兵部队。

一个 \(N\times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 \(\texttt{H}\) 表示），也可能是平原（用 \(\texttt{P}\) 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

对于 \(100\%\) 的数据，\(N\le 100\)，\(M\le 10\)，保证字符仅包含 p 与 h。

状压神仙题

考虑压缩一行上每列的状态，然后再一行行的搞

具体地，我们记录每一行所有列是否可以放炮兵

然后预处理所有合法的放炮兵的方法（不考虑地图的状况）

枚举转移即可，注意要滚动数组，还要单独处理前两行

时间复杂度 \(O(n2^{3m}) = O(n8^m)\)

代码：（f[i][j][k]表示前两行的状态是i和j，k是滚动数组）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1024+5)

char x;
int n,m,res,mx,st[N],f[N][N][3],F[105],sum[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; mx=(1<<m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> x,F[i]=(F[i]<<1)+(x=='H');
    for(int i=0; i<mx; i++)
    {
        sum[i]=__builtin_popcount(i); // 不建议使用，我是懒得写 qwq
        st[i]=((i&(i<<1))==0)&&((i&(i<<2))==0);
    }
    for(int i=0; i<mx; i++)
        if(st[i]&&((i&(F[1]))==0))
            f[0][i][0]=sum[i];
    for(int i=0; i<mx; i++)
        for(int j=0; j<mx; j++)
            if(st[i]&&st[j]&&((i&j)==0)&&((i&F[1])==0)&&((j&F[2])==0))
                f[i][j][1]=sum[i]+sum[j];
    for(int t=2; t<n; t++)
        for(int i=0; i<mx; i++)
        {
            if((!st[i])||(i&F[t-1])) continue;
            for(int j=0; j<mx; j++)
            {
                if((!st[j])||(j&F[t])||(i&j)) continue;
                for(int k=0; k<mx; k++)
                {
                    if((!st[k])||(i&k)||(j&k)||(k&F[t+1])) continue;
                    f[j][k][t%3]=max(f[j][k][t%3],f[i][j][((t-1)%3+3)%3]+sum[k]);
                }
            }
        }
    for(int i=0; i<mx; i++)
        for(int j=0; j<mx; j++)
            res=max(res,f[i][j][((n-1)%3+3)%3]);
    cout << res << '\n';
    return 0;
}