[POJ1185]炮兵阵地
试题描述
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
输出
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
输入示例
5 4 PHPP PPHH PPPP PHPP PHHP
输出示例
6
数据规模及约定
见“输入”
题解
观察到 m 很小，所以很自然想到状态压缩。这里我们还需要一个工作，不妨用程序统计一下 m = 10 时一行中可行的摆放方案有多少种，就是 210 枚举一下，然后排掉那些挨得太近的情况，发现只有 60 种。于是就可以设 f(i, j, k) 表示考虑前 i 行，最后两行放置炮兵的集合分别为 j 和 k，我们把那 60 种方案离散一下就可以 dp 了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 110
#define maxm 15
int n, m, St[maxn], f[maxn][maxn][maxn];
char Map[maxn][maxm];
void up(int& a, int b) {
a = max(a, b);
return ;
}
void print(int x) {
int num[15], cnt = 0;
memset(num, 0, sizeof(num));
while(x) num[++cnt] = x & 1, x >>= 1;
for(int i = 1; i <= 4; i++) putchar(num[i] + '0');
putchar(' ');
return ;
}
int main() {
n = read(); m = read();
for(int i = 1; i <= n; i++) scanf("%s", Map[i] + 1);
int all = (1 << m) - 1, cnt = 0;
for(int i = 0; i <= all; i++) {
bool ok = 1;
for(int j = 0; j < m; j++)
if((i >> j & 1) && ((i >> j + 1 & 1) || (i >> j + 2 & 1))) {
ok = 0; break;
}
if(ok) St[++cnt] = i;
}
// for(int i = 1; i <= cnt; i++) print(St[i]); putchar('
');
memset(f, -1, sizeof(f));
f[0][1][1] = 0;
for(int i = 0; i < n; i++)
for(int j = 1; j <= cnt; j++)
for(int k = 1; k <= cnt; k++) if(f[i][j][k] >= 0) {
int S1 = St[j], S2 = St[k];
for(int l = 1; l <= cnt; l++) if(!(S1 & St[l]) && !(S2 & St[l])) {
int S = St[l];
bool ok = 1; int cal = 0;
for(int x = 0; x < m; x++) {
if((S >> x & 1) && Map[i+1][x+1] == 'H') {
ok = 0; break;
}
cal += (S >> x & 1);
}
if(!ok) continue;
up(f[i+1][k][l], f[i][j][k] + cal);
// printf("to: %d ", i + 1); print(S2); print(S);
// printf("%d %d %d
", f[i+1][k][l], f[i][j][k], cal);
}
// printf("%d ", i); print(S1); print(S2); printf("%d
", f[i][j][k]);
}
int ans = -1;
for(int i = 1; i <= cnt; i++)
for(int j = 1; j <= cnt; j++) up(ans, f[n][i][j]);
printf("%d
", ans);
return 0;
}
终于在 POJ 上看到一道中文题。。。