总时间限制: 2000ms  内存限制: 65536kB

描述

司令部的将军们打算在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

来源

Noi 01

【分析】

这是一道状压DP

G[i][s1][s2] : 截至第i行，第i-1行按照s1放置，第i行按照s2放置，能布置的炮兵最大数目

这里面有个小问题，算是这道题的难点：如果直接表示s1, s2，数组开不下（没法用滚动数组），因此我们给每个状态编号，用编号代替状态。经测试，N=10时状态数最多60，这样就完全开的下了。

另外，在判断一个状态是否合法时，可以用位运算的技巧（n&(n<<1), n&(n<<2)）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <sstream>
using namespace std;
#define _for(i,a,b) for(int i = (a); i < (b); ++i)int N, M;
int m[105];
vector<int> s; // 最大60
int G[105][70][70];void setBit(int& n, int i, bool v){if(v) n |= (1<<i);else n &= ~(1<<i);
}
int countBit(int n){int rt = 0;while(n != 0){n &= (n-1);++rt;}return rt;
}
string printBit(int n, int l){stringstream ss;for(int i = 0; i < l; ++i)ss << ((n>>i)&1);return ss.str();
}void in(){cin >> N >> M;_for(i, 0, N) _for(j, 0, M){char c;cin >> c;if(c == 'H') setBit(m[i], j, 1);}for(int i = 0; i < (1<<M); ++i){if(i & (i<<1)) continue;if(i & (i<<2)) continue;s.push_back(i);}
}int main(){in();int ans = 0;if(N == 1){for(int e : s) if(!(e&m[0])) ans = max(ans, countBit(e));cout << ans << endl;return 0;}ans = 0;for(int i = 0; i < s.size(); ++i){for(int j = 0; j < s.size(); ++j){if(s[i]&m[0]) continue;if(s[j]&m[1]) continue;if(s[i]&s[j]) continue;G[1][i][j] = countBit(s[i])+countBit(s[j]);ans = max(ans, G[1][i][j]);// printf("G[%d][%s][%s] = %d\n", 1, printBit(s[i], M).c_str(), printBit(s[j], M).c_str(), G[1][i][j]);}}if(N == 2){cout << ans << endl;return 0;}for(int i = 2; i < N; ++i){for(int j2 = 0; j2 < s.size(); ++j2){if(s[j2]&m[i]) continue;for(int j1 = 0; j1 < s.size(); ++j1){if(s[j1]&m[i-1]) continue;if(s[j1]&s[j2]) continue;for(int j0 = 0; j0 < s.size(); ++j0){if(s[j0]&m[i-2]) continue;if(s[j0]&s[j1]) continue;if(s[j0]&s[j2]) continue;G[i][j1][j2] = max(G[i][j1][j2], G[i-1][j0][j1]+countBit(s[j2]));}// printf("G[%d][%s][%s] = %d\n", i, printBit(s[j1], M).c_str(), printBit(s[j2], M).c_str(), G[i][j1][j2]);}}}ans = 0;_for(i,0,s.size()) _for(j,0,s.size()) {ans = max(ans, G[N-1][i][j]);}cout << ans << endl;system("pause");return 0;
}