参考视频:
【E27 状态压缩DP 炮兵部队】 https://www.bilibili.com/video/BV1vy4y1z7qy/?share_source=copy_web&vd_source=859acc3f9fc77bd4a4a2953cd1bcab12

本题与玉米田不同的是, 玉米田只要我们求存在多少种合法状态, 而本题要我们求能合法摆放的炮兵的数量是多少, 所以我们需要额外记录一个 $num$ 数组来表示每种合法状态的数量

由于攻击范围是 2 格, 所以要判断两行的合法状态

行内合法: 如果 $!(i\;\&\;i\gg1)\;\&\&\;!(i\;\&\;i\gg2)$ 为真, 则 $i$ 合法

行间合法: $s[a]$ 为第 $i$ 行, $s[b]$ 为第 $i-1$ 行, $s[c]$ 为第 $i-2$​ 行

其中 $s[i]$ 表示预处理出的行内合法状态, $a, b, c$ 是下标

如果
$$!(s[a]\;\&\;s[b])\;\&\&\;!(s[b]\;\&\;s[c])\;\&\&\;\\!(s[a]\;\&\;s[c])\;\&\&\;(s[a]\;\&\;g[i])==s[a]$$
为真,

则行间合法 (同列相邻两行间不能同时摆放, 间隔一行的两行间也不能同时摆放, 而且当前状态要适配地形)

状态表示:

$f(i,s[a],b)$ 表示已经摆放前 $i$ 行, 当前是第 $i$ 行第 $s[a]$ 个状态, 并且第 $i-1$ 行为第 $s[b]$ 个状态时, 能摆放的最大数量; $num(s[a])$ 表示 $s[a]$ 状态下, 一行能摆放的炮兵的数量

$f(i-1, s[b], s[c])+num(s[a])\rightarrow f(i, s[a], s[b])$

C++ 代码

预处理

void init() {
    cin>>n>>m;
    //预处理地图
    for(int i=1; i<=n; i++)
        for(int j=0; j<m; j++) {
            char c; cin>>c;
            if(c=='P') g[i]+=1<<(m-j-1);
        }

    //预处理行内的合法状态数
    for(int i=0; i<1<<m; i++) 
        if(!(i>>1&i)&&!(i>>2&i)){
            s[cnt++]=i;
            for(int j=0; j<m; j++)
                num[i]+=(i>>j&1);
        }
}

如果开一个三维数组 $f[N][2^{10}][2^{10}]$ , 所需空间为 $110\times1024\times1024\times4=440MB$ , 空间会爆掉, 所以需要对空间进行优化

由状态转移方程我们发现, 只会用到 $i-1$ 层空间, 所以我们可以用一个 二维的滚动数组, 将空间的大小优化到 8MB

由于 $i$ 从 $1\sim n$ 枚举, 我们使用滚动数组时可以对 $i$ 取模, 一种取模的方法是: $i\;\&\;1$​

状态递推

void solve() {

    init();

    for(int i=1; i<=n+2; i++)  //多循环两次, 方便统计结果
        for(int a=0; a<cnt; a++)  //枚举第i行状态
            for(int b=0; b<cnt; b++)  //枚举第i-1行状态
                for(int c=0; c<cnt; c++)  //枚举第i-2行状态
                    if(
                        !(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) &&
                        (s[a]&g[i])==s[a]
                      )
                      f[i&1][a][b]=max(f[i&1][a][b], f[i-1&1][b][c]+num[s[a]]);

    cout<<f[n+2&1][0][0];
}