【洛谷题解/NOI2001】P2704/NOI2001炮兵阵地

原题链接：https://www.luogu.com.cn/problem/P2704
难度：提高+/省选-
涉及知识点：状态压缩DP

题意

在一个 $n\times m$ 的方阵上，有平原( P )或山地( H )，只有在平原上才能放炮兵部队。炮兵部队的射程范围是上、下、左、右各延展2格。求在各炮兵部队不会互相攻击到的情况下，最多能够放置多少个炮兵部队。

分析与解决

这道题着眼一看，是一道很经典的棋盘式状态压缩DP，是对【SCOI2005】互不侵犯一题的简单扩展，主要是攻击范围由 1 格提升到了 2 格。

在 【互不侵犯】 一题中，我们对状态的合法性检查时每两列一查，而对状态转移的合法性检查也是每两行一查。那么扩展到 【炮兵阵地】 这题，我们就可以考虑每三行一检查即可。

设 $f[i][j][k]$ 为摆完前 $i$ 行后，第 $i-1$ 行的状态为 $j$，第 $i-2$ 行的状态为 $k$ 的状态表示。在输入时，为了方便后续处理山地的问题，我们用 0 表示平原，用 1 表示山地。首先预处理所有合法状态，不合法的状态就是当第 $i-2$ 行为 1 时（固定），第 $i$ 行或第 $i-1$ 行中的任意一行也为 1，此时无法部署炮兵部队，无法转移到这种状态。由于最后答案要求最多可以部署的炮兵部队数量，我们也需要在预处理时预处理各状态的炮兵部队数量。

三层循环行数、第 $i-1$ 行状态、第 $i$ 行状态，第 $i-2$ 行状态，如果三种状态之间存在同一列有多于 1 个的炮兵部队，那么不合法；如果第 $i-1$ 行和第 $i$ 行的对应位置为山地，则无法部署炮兵部队，不合法。状态转移方程为：
f [ i ] [ j ] [ k ] = max ⁡ { f [ i − 1 ] [ i − 2 ] [ i − 1 ] + c n t [ i − 1 ] } f[i][j][k]=\max\left\{f[i-1][i-2][i-1]+cnt[i-1]\right\} f[i][j][k]=max{f[i−1][i−2][i−1]+cnt[i−1]}

AC代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 15, M = 1 << 10;

int n, m;
int g[110];
vector <int> state;
int f[2][M][M], cnt[M];

bool check(int state)
{
	for (int i = 0; i < m; i++)
	{
		if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1))) return false;
	}
	return true;
}

int count(int state)
{
	int res = 0;
	for (int i = 0; i < m; i++) res += state >> i & 1;
	return res;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char c;
			cin >> c;
			if (c == 'H') g[i] += 1 << j;
		}
	}
	
	for (int i = 0; i < 1 << m; i++)
	{
		if (check(i)) 
		{
			state.push_back(i);
			cnt[i] = count(i);
		}
	}
	
	for (int i = 1; i <= n + 2; i++)
	{
		for (int j = 0; j < state.size(); j++)
		{
			for (int k = 0; k < state.size(); k++)
			{
				for (int u = 0; u < state.size(); u++)
				{
					int a = state[j], b = state[k], c = state[u];
					if ((a & b) || (b & c) || (a & c)) continue;
					if (g[i - 1] & a | g[i] & b) continue;
					f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
				}
			}
		}
	}
	
	cout << f[n + 2 & 1][0][0];
	return 0;
}