题意简述

给定一张地图，有山地H，平原P，平原可放置炮兵，

炮兵可以攻击沿横向左右各两格，沿纵向上下各两格的区域

求最多放几个炮兵，使他们两两攻击不到

题解思路

枚举第i层，第i - 1层，第i - 2层的状态，滚动数组

dp[i & 1][j][k] = max(dp[(i + 1) & 1][k][l] + __builtin_popcount(j));

代码

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, M, ans;

int map[110];

int dp[3][1050][1050];

char ch;

void maxx(int &x, int y) {x = max(x, y); }

int main()

{

	ios::sync_with_stdio(false);

	cin >> n >> m;

	for (register int i = 1; i <= n; ++i)

		for (register int j = 1; j <= m; ++j)

		{

			cin >> ch;

			if (ch == 'P') map[i] <<= 1;

			else map[i] = map[i] << 1 | 1;

		}

	M = 1 << m;

	for (register int i = 1; i <= n; ++i)

		for (register int j = 0; j < M; ++j)

			if (!(j & map[i]) && !(j & j << 1) && !(j & j << 2))

				for (register int k = 0; k < M; ++k)

					if (!(k & j) && !(k & k << 1) && !(k & k << 2))

						for (register int l = 0; l < M; ++l)

							if (!(j & l) && !(j & k) && !(l & l << 1) && !(l & l << 2))

								maxx(dp[i & 1][j][k], dp[(i + 1) & 1][k][l] + __builtin_popcount(j));

	for (register int i = 0; i < M; ++i)

		for (register int j = 0; j < M; ++j)

			maxx(ans, dp[n & 1][i][j]);

	cout << ans << endl;

}