题目描述

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

输出样例

解题思路

看到这个玄学的数据范围，第一反应就是状压DP

我们设 $dp[i][j][k]$ 表示当前正在摆放第 $i$ 行，当前行的状态编号为 $j$ ，上一行的状态编号为 $k$ 时的最大数量

我们先把所有的可能状态预处理出来，记为 stats[]

初始状态时所有的dp[1][i][1] = Popcount(stats[i])，其中 Popcount(x)表示x的二进制1的个数

转移方程显然， $dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] +$ Popcount(stats[j]) $)$ ，
其中 $j$ 表示当前行的状态编号， $k$ 表示上一行的， $l$ 表示再上一行的

注意判一下地形是否符合，方法参见洛谷P1879

我要开滚动数组

代码实现

//
//  29.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/1/29.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include 
#include 
#include 
#include 

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 100 + 10;
const int MAXM = 10 + 5;
const int MAX = (1 << 10) - 1 + 10;

int status[MAX], dp[2][MAX][MAX], can[MAXN];
int cnt, n, m;
char str[MAXM];

inline int pop(int x) {
    int ret = 0;
    while(x) {
        if(x & 1) ret++;
        x >>= 1;
    }
    return ret;
}

inline int Check(int a, int b) {
    return a & b;
}

inline int Check3(int a, int b, int c) {
    return Check(a,b) || Check(a,c) || Check(b,c);
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%s",str + 1);
        for(int j = 1; j <= m; ++j)
            if(str[j] == 'H')can[i] = (can[i] << 1) | 1;
            else can[i] = can[i] << 1;
    }
    for(int i = 0; i <= (1 << m) - 1; ++i) {
        if((!(i & (i << 2))) && (!(i & (i << 1))))
            status[++cnt] = i;
    }
    for(int i = 1; i <= cnt; ++i)
        dp[1 % 2][i][1] = pop(status[i]);

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            if (!(status[j] & can[i])) {
                for (int k = 1; k <= cnt; ++k) {
                    if ((!(status[k] & can[i - 1])) && (!Check(status[j],status[k]))) {
                        for (int l = 1; l <= cnt; ++l){
                            if ((!(status[l] & can[i - 2])) && (!Check3(status[j], status[k], status[l])))
                                dp[i % 2][j][k] = std::max(dp[i % 2][j][k], dp[(i - 1) % 2][k][l] + pop(status[j]));
                        }
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= cnt; ++i)
        for(int j = 1; j <= cnt; ++j)
            ans = std::max(ans, dp[n % 2][i][j]);
    printf("%d\n", ans);
    return 0;
}

炮兵阵地