题目
总时间限制: 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
思路
状态压缩动态规划，没有见过这种算法就会很困难. 作为自学的练习题做了，感觉细节挺多，写起来较有难度.
状态压缩指用编码简洁表示多维信息的方法. 此题可用二进制编码表示每一行摆放炮兵的情况，第位为
表示该行第
列放置了炮兵.
设为已知前
行情况且第
行编码为
、第
行编码为
时的最大摆放数. 则不难发现
.
合法指该行自身的炮兵之间互不影响且不和前后两行的炮兵影响，指编码
中炮兵的数量.
是 base case，很好处理. 在
为最后一行、
合法的的所有
值里取最大得到结果.
原始加注释代码：
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#define MAXL 111
#define MAXD 10
#define IOS_SPEED std::ios::sync_with_stdio(false)
using std::cin;
using std::cout;
using std::array;
using std::max;
using std::vector;
int rows, cols, upper; // 行数, 列数, 状态编码的上界
array<int, MAXL> room{0}; // 表示每一行哪些位置可以摆放炮兵的二进制编码, 1 为可以摆放
array<array<array<int, (1<<MAXD)>, (1<<MAXD)>, MAXL> answer; // 上述 M 数组
vector<int> nums_range; // 所有自我不矛盾(即同行内炮兵范围不干扰)的状态编码
inline int one_count(int state){ // 状态编码的 1 即炮兵的数目
int result = 0;
for(int i=0; i<cols; i++){
result += state&1; state >>= 1;
}
return result;
}
inline bool has_room(int state, int row){ // 状态编码是否在该行可摆放的位置摆放, 否则淘汰
return (row<0)||((state|room[row])==room[row]); // state|room[row] 会保留 room 编码中的 1
}
inline bool no_self_conflict(int state){ // 状态编码行内的炮兵是否有干扰, 否则预先淘汰
int cur = -1e1; // 记录每个 1 出现的数位
for(int i=0; i<cols; i++){
if(state&1){
if(i<=cur+2) return false; // 相邻两个 1 相距不超过 2, 有干扰
cur = i;
}
state >>= 1;
}
return true;
}
void find_nums_range(){ // 排除自干扰的状态编码
for(int i=0; i<upper; i++) if(no_self_conflict(i)) nums_range.push_back(i);
}
int find_answer(){
find_nums_range();
for(int i: nums_range){ // base case: r==0
if(!has_room(i, 0)) continue; // 排除越位放置，下同
for(int j: nums_range){
answer[0][i][j] = one_count(i); // 直接计编码的 1 数
}
}
for(int r=1; r<rows; r++){ // 枚举行 r
for(int i: nums_range){ // 枚举第 r 行的可行编码 i
if(!has_room(i, r)) continue;
for(int j: nums_range){ // 枚举第 r-1 行的可行编码 j
if(!has_room(j, r-1)) continue;
if(j&i) continue; // 排除前后行同列放置，下同
int max_prev = 0;
for(int prev: nums_range){ // 枚举第 r-2 行的可行编码 prev
if(!has_room(prev, r-2)) continue;
if((prev&j)||(prev&i)) continue;
max_prev = max(max_prev, answer[r-1][j][prev]);
}
answer[r][i][j] = max_prev+one_count(i);
}
}
}
int max_answer = 0;
for(int i: nums_range){ // 寻找结果: r==rows-1
if(!has_room(i, rows-1)) continue;
for(int j: nums_range){
if(!has_room(j, rows-2)) continue;
if(j&i) continue;
max_answer = max(max_answer, answer[rows-1][i][j]);
}
}
return max_answer;
}
void interface(){
IOS_SPEED;
cin >> rows >> cols;
upper = 1<<cols;
char new_grid;
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
cin >> new_grid;
if(new_grid=='P') room[i] += (1<<j);
}
}
cout << find_answer() << "\n";
nums_range.clear();
}
int main()
{
interface();
return 0;
}
上述程序的空间占用较大，因为所有非自干扰的状态编码是确定的，不需要在 answer 数组中直接以值较大的编码（可达）作为下标，只需给每个这样的状态编码一个序号，以序号作为下标（经试验，长度为
、非自干扰的编码个数不超过
）. 因此可有如下优化：
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#define MAXL 111
#define MAXD 10
#define IOS_SPEED std::ios::sync_with_stdio(false)
using std::cin;
using std::cout;
using std::array;
using std::max;
using std::vector;
int rows, cols, upper;
array<int, MAXL> room{0};
array<array<array<int, MAXD*MAXD>, MAXD*MAXD>, MAXL> answer;
vector<int> range;
inline int one_count(int state){
int result = 0;
for(int i=0; i<cols; i++){
result += state&1; state >>= 1;
}
return result;
}
inline bool has_room(int state, int row){
return (row<0)||((state|room[row])==room[row]);
}
inline bool no_self_conflict(int state){
int cur = -1e1;
for(int i=0; i<cols; i++){
if(state&1){
if(i<=cur+2) return false;
cur = i;
}
state >>= 1;
}
return true;
}
void find_nums_range(){
for(int i=0; i<upper; i++) if(no_self_conflict(i)) range.push_back(i);
}
int find_answer(){
find_nums_range();
for(int i=0; i<range.size(); i++){
if(!has_room(range[i], 0)) continue;
for(int j=0; j<range.size(); j++){
answer[0][i][j] = one_count(range[i]);
}
}
for(int r=1; r<rows; r++){
for(int i=0; i<range.size(); i++){
if(!has_room(range[i], r)) continue;
for(int j=0; j<range.size(); j++){
if(!has_room(range[j], r-1)) continue;
if(range[j]&range[i]) continue;
int max_prev = 0;
for(int prev = 0; prev<range.size(); prev ++){
if(!has_room(range[prev], r-2)) continue;
if((range[prev]&range[j])||(range[prev]&range[i])) continue;
max_prev = max(max_prev, answer[r-1][j][prev]);
}
answer[r][i][j] = max_prev+one_count(range[i]);
}
}
}
int max_answer = 0;
for(int i=0; i<range.size(); i++){
if(!has_room(range[i], rows-1)) continue;
for(int j=0; j<range.size(); j++){
if(!has_room(range[j], rows-2)) continue;
if(range[j]&range[i]) continue;
max_answer = max(max_answer, answer[rows-1][i][j]);
}
}
return max_answer;
}
void interface(){
IOS_SPEED;
cin >> rows >> cols;
upper = 1<<cols;
char new_grid;
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
cin >> new_grid;
if(new_grid=='P') room[i] += (1<<j);
}
}
cout << find_answer() << "\n";
range.clear();
}
int main()
{
interface();
return 0;
}
