【传送门】
【题目大意】
司令部的将军们打算在 \(N\times M\) 的网格地图上部署他们的炮兵部队。一个 \(N\times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
求最多能摆放的炮兵部队的数量。
【关键词】
- 状压DP
- 预处理
- 进制运算
【分析】
可以说这道题是状压\(DP\)的经典例题了，我们思考，每一行的状态只会被当前这一行的地形和前两行的状态束缚，所以我们可以预处理第一行与第二行，然后枚举每一行的状态进行\(DP\)转移。
细节方面就看代码吧。
【Code】
//#include<bits/stdc++.h>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug() puts("FBI WARNING!")
#define ll long long
using namespace std;
inline int read(){
int f = 1, x = 0;char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');
do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f*x;
}
int n, m, M;
int maps[105], num[(1<<11)], c[80], len;
char tmp[15];
int dp[105][80][80], ans;
inline bool judge(int a, int b) {
if ((a & b) == 0) return 1;
else return 0;
}
inline bool can(int x) {
if (((x << 1) & x) || (x << 2) & x || (x >> 1) & x || (x >> 2) & x) return 0;
else return 1;
}
inline void init() {
/*
预处理num[]
*/
for (int i = 1;i < M; ++i) {
int x = i;
while (x) {
num[i]+=x%2;
x >>= 1;
}
}
/*
预处理c[]
*/
for (int i = 0;i < M; ++i) {
if (can(i)) {
c[++len] = i;
}
}
}
int main(){
n = read(); m = read();
M = (1 << m);
init();
for (int i = 1;i <= n; ++i) {
scanf("%s", tmp);
for (int j = 0;j < m; ++j)
if (tmp[j] == 'H')
maps[i] += (1 << j);
}
/*for (int i = 0;i < n; ++i) {
printf("%d\n", maps[i]);
}*/
for (int i = 1;i <= len; ++i) { // 第一行处理
if (judge(c[i], maps[1]))
dp[1][i][1] = num[c[i]];
}
/*for (int i = 0;i < M; ++i) {
printf("dp[0][%d][0] = %d can:%d, judge:%d\n", i, dp[0][i][0], can(i), judge(i, maps[0]));
}*/
for (int i = 1;i <= len; ++i) { // 第二行处理
if (judge(c[i], maps[2]))
for (int j = 1;j <= len; ++j) {
if (judge(c[j], maps[1]) && judge(c[i], c[j]))
dp[2][i][j] = max(dp[2][i][j], dp[1][j][1]+num[c[i]]);
}
}
for (int i = 3;i <= n; ++i) { // DP
for (int j = 1;j <= len; ++j) {
if (judge(c[j], maps[i]))
for (int k = 1;k <= len; ++k) {
if (judge(c[j], c[k]) && judge(c[k], maps[i-1])) {
for (int s = 1;s <= len; ++s) {
if (judge(c[s], c[j]) && judge(c[s], c[k]) && judge(c[s], maps[i-2])) {
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][s]+num[c[j]]);
}
}
}
}
}
}
for (int i = 1;i <= len; ++i) { //求解答案
for (int j = 1;j <= len; ++j) {
ans = max(ans, dp[n][i][j]);
}
}
printf("%d", ans);
return 0;
}