【题目来源】
洛谷：P2704 [NOI2001] 炮兵阵地 - 洛谷
【题目描述】
司令部的将军们打算在 \(N×M\) 的网格地图上部署他们的炮兵部队。
一个 \(N×M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 \(H\) 表示），也可能是平原（用 \(P\) 表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
【输入】
第一行包含两个由空格分割开的正整数，分别表示 \(N\) 和 \(M\)。
接下来的 \(N\) 行，每一行含有连续的 \(M\) 个字符，按顺序表示地图中每一行的数据。
【输出】
一行一个整数，表示最多能摆放的炮兵部队的数量。
【输入样例】
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
【输出样例】
6
【算法标签】
《洛谷 P2704 炮兵部队》 #进制# #状压DP# #NOI# #2001#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 150, M = 1<<15; // N 表示最大行数，M 表示最大状态数（2^15）
int n, m, cnt; // n 表示行数，m 表示列数，cnt 表示有效状态的数量
int g[N], s[N], num[M]; // g[i] 表示第 i 行的地形状态，s[i] 表示第 i 个有效状态，num[i] 表示状态 i 中放置的士兵数量
int f[N][N][N]; // f[i][a][b] 表示前 i 行，第 i 行状态为 s[a]，第 i-1 行状态为 s[b] 时的最大士兵数量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=='P') g[i] += 1<<(m-j-1); // 如果当前位置是 'P'，则在 g[i] 中标记为 1}// 预处理所有有效的状态for (int i=0; i<(1<<m); i++)if (!(i&i>>1) && !(i&i>>2)) // 检查状态 i 是否有效（没有两个相邻的 1）{s[cnt++] = i; // 将有效状态存入 s 数组for (int j=0; j<m; j++)num[i] += (i>>j&1); // 计算状态 i 中 1 的个数，即士兵数量}// 动态规划求解最大士兵数量for (int i=1; i<=n+2; i++) // 遍历每一行，多处理两行以确保边界条件for (int a=0; a<cnt; a++) // 遍历第 i 行的所有有效状态for (int b=0; b<cnt; b++) // 遍历第 i-1 行的所有有效状态for (int c=0; c<cnt; c++) // 遍历第 i-2 行的所有有效状态if (!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) && // 检查三行状态是否互不冲突(g[i]&s[a])==s[a] && (g[i-1]&s[b])==s[b]) // 检查状态是否与地形匹配f[i][a][b] = max(f[i][a][b], f[i-1][b][c] + num[s[a]]); // 更新状态转移方程cout << f[n+2][0][0] << endl; // 输出最终结果return 0;
}
【运行结果】
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
6