题目

[NOI2001] 炮兵阵地

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

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

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

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

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

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

对于 $100\%$ 的数据， $N\le 100$ ， $M\le 10$ ，保证字符仅包含 P 与 H。

题解

首先看到数据范围，直接状态压缩dp

考虑设计状态

先尝试f[i][j]表示推到第i行，且第i行的状态的二进制为j的，能放下的最多的炮兵部队

尝试转移

f[i][j]要从f[i-1][~]转移过来，但f[i-1][~]的状态包含的集合又不是都能用，所以没法转移

考虑加状态

f[i][j][fl]表示推到第i行，且第i行的状态的二进制为j的，第i-1行的状态为fl的，能放下的最多的炮兵部队

可以转移了

实现

判断是否能放，二进制和地图与一下，二进制本身分别和其左移一位、两位与一下

其余同理

出现问题

1.状压dp最好下标从0开始

2.学习了滚动数组

代码

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int n, m;

int Map[110];//如果是1表示山地，0表示平原 

int f[3][1 << 10][1 << 10]; // i，当前状态，上一行状态 
int num_of_1[1 << 10];


int getsum(int x)
{
	int ans = 0;
	while(x)
	{
		x &= (x - 1);
		ans++;
	}
	return ans;
}

int main()
{

	for(int i = 0;i < (1 << 10);i++)
	{
		num_of_1[i] = getsum(i);
	}

	n = read(), m = read();
	char ch;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			cin >> ch;
			if(ch == 'H')
			{
				Map[i] |= (1 << j);
			}
		}
	}

	for(int j = 0;j < (1 << m);j++)
	{
		if(j & (j << 1) || j & (j << 2) || j & Map[0]) continue;
		f[0][j][0] = num_of_1[j];
	}

	for(int j = 0;j < (1 << m);j++)
	{
		for(int fl = 0;fl < (1 << m);fl++)
		{
			if(j & (j << 1) || j & (j << 2) || j & Map[1] || fl & (fl << 1) || fl & (fl << 2) || fl & Map[0] || j & fl || j & Map[1])
				continue;
			f[1][j][fl] = num_of_1[j] + num_of_1[fl];
		}
	}

	for(int i = 2;i < n;i++)
	{
		for(int j = 0;j <= (1 << m) - 1;j++)//当前行 
		{
			if(j & Map[i] || j & (j << 1) || j & (j << 2))
			{
				continue;
			}
		
			for(int fl = 0; fl <= (1 << m) - 1;fl++)//上一行 
			{
				if(fl & Map[i - 1] || fl & (fl << 1) || fl & (fl << 2) || j & fl)
				{
					continue;
				}
			
				for(int fll = 0; fll < (1 << m);fll++)
				{
					if(fll & Map[i - 2] || fll & (fll << 1) || fll & (fll << 2) || j & fll || fl & fll)
					{
						continue;
					}
				
					f[i % 3][j][fl] = max(f[i % 3][j][fl], f[(i - 1) % 3][fl][fll] + num_of_1[j]);
				
				}
			}
		}
	}


	int ans = 0;

	for(int j = 0;j < (1 << m);j++)
	{
		for(int fl = 0;fl < (1 << m);fl++)
		{
			ans = max(ans, f[(n - 1) % 3][j][fl]);
		}
	}

	cout << ans << endl;
	return 0;
}