洛谷

洛谷题单指南-状态压缩动态规划-P2704 [NOI2001] 炮兵阵地

原题链接：https://www.luogu.com.cn/problem/P2704

题意解读：一个炮兵部队可以覆盖横向纵向两行的位置，给定n*m区域，可以部署炮兵为P，不能部署炮兵为H，求不互相攻击的情况下最多可以部署多少炮兵部队。

解题思路：

通过对一行是否部署炮兵部署，可以使用二进制整数来压缩状态。

由于当前行的状态，与前两行的状态有关，状态可以如此定义：

设f[i][j][k]表示前i行已经部署完，第i行状态是j，第i-1行状态是k的最多炮兵部队数

使用mask[]来保存每一行每个位置是否可以部署炮兵的情况：

for(int i = 1; i <= n; i++)
{
    for(int j = 0; j < m; j++)
    {
        char x;
        cin >> x;
        if(x == 'H') mask[i] |= (1 << j); //将一行山地位置用二进制1表示
    }
}

预处理所有本行内合法的状态，同时计算每个状态中1的个数，减少枚举范围：

for(int i = 0; i < 1 << m; i++)
{
    if((i & i << 1) || (i & i << 2)) continue; //状态中存在11或者101
    stat.push_back(i);
    count(i);
}

下面进行初始化，主要针对第一行进行赋初值：

for(auto s : stat) 
{
    if(mask[1] & s) continue;
    f[1][s][0] = cnt[s];
    ans = max(ans, f[1][s][0]);
}

接下来，从第2行开始枚举所有行i，枚举第i、i-1、i-2行的状态j，k，l，实现状态转移：

f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + cnt[j])

更新答案：

ans = max(ans, f[i][j][k])

如果空间不够用，还可以将第一维用滚动数组优化，这里直接AC了，就省了这一步。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105, M = 10;
int mask[N], cnt[1 << M];
int f[N][1 << M][1 << M]; //f[i][j][k]表示前i行已经部署完，第i行状态是j，第i-1行状态是k的最多炮兵部队数
vector<int> stat; //一行合法的状态
vector<int> mp[1 << M]; //合法的状态转移
int n, m, ans;

void count(int x)
{
    int res = 0;
    for(int i = 0; i < m; i++)
        if(x >> i & 1) res++;
    cnt[x] = res; //保存x二进制中1的个数
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            char x;
            cin >> x;
            if(x == 'H') mask[i] |= (1 << j); //将一行山地位置用二进制1表示
        }
    }

    for(int i = 0; i < 1 << m; i++)
    {
        if((i & i << 1) || (i & i << 2)) continue; //状态中存在11或者101
        stat.push_back(i);
        count(i);
    }
    //初始化第一行
    for(auto s : stat) 
    {
        if(mask[1] & s) continue;
        f[1][s][0] = cnt[s];
        ans = max(ans, f[1][s][0]);
    }
    //dp过程
    for(int i = 2; i <= n; i++) //从第2行开始枚举
    {
        for(auto j : stat) //第i行的状态
        {
            if(mask[i] & j) continue; //第i行状态不合法
            for(auto k : stat) //第i - 1行的状态
            {
                if((mask[i - 1] & k) || k & j) continue; //第i - 1行状态不合法
                for(auto l : stat) //第i - 2行的状态
                {
                    if((mask[i - 2] & l) || l & k || l & j) continue; //第i - 2行状态不合法
                    f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + cnt[j]);
                }
                ans = max(ans, f[i][j][k]);
            }
        }
    }

    cout << ans;
    return 0;
}