【题解】POJ 1185,LG P2704【炮兵阵地】

【传送门】

• POJ 1185
• 洛谷 P2704

【题目大意】

司令部的将军们打算在 \(N×MN\times MN×M\) 的网格地图上部署他们的炮兵部队。一个 \(N×MN\times MN×M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

【输入格式】

第一行包含两个由空格分割开的正整数，分别表示 \(N\) 和 \(M\)；(\(N≤100,M≤10\))
接下来的 \(N\) 行，每一行含有连续的 \(M\) 个字符(P 或者 H)，中间没有空格。按顺序表示地图中每一行的数据。

【输出格式】

仅一行，包含一个整数 \(K\)，表示最多能摆放的炮兵部队的数量。

【样例输入】

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

【样例输出】

6

【关键词】

• 状压DP
• 预处理
• 进制运算

【题解】

可以说这道题是状压\(DP\)的经典例题了，我们思考，每一行的状态只会被当前这一行的地形和前两行的状态束缚，所以我们可以预处理第一行与第二行，然后枚举每一行的状态进行\(DP\)转移。

细节方面就看代码吧。

【code】

//#include<bits/stdc++.h>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug() puts("FBI WARNING!")
#define ll long long

using namespace std;
inline int read(){
    int f = 1, x = 0;char ch;
    do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');
    do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9'); 
    return f*x;
}
int n, m, M;
int maps[105], num[(1<<11)], c[80], len;
char tmp[15];
int dp[105][80][80], ans;

inline bool judge(int a, int b) {
    if ((a & b) == 0) return 1;
    else return 0;
}

inline bool can(int x) {
    if (((x << 1) & x) || (x << 2) & x || (x >> 1) & x || (x >> 2) & x) return 0;
    else return 1;
}

inline void init() {
    /*
    预处理num[] 
    */
    for (int i = 1;i < M; ++i) {
        int x = i;
        while (x) {
            num[i]+=x%2;
            x >>= 1;
        }
    }
    /*
    预处理c[]
    */
    for (int i = 0;i < M; ++i) {
        if (can(i)) {
            c[++len] = i;
        }
    }
}

int main(){
    n = read(); m = read();
    M = (1 << m);
    init();
    for (int i = 1;i <= n; ++i) {
        scanf("%s", tmp);
        for (int j = 0;j < m; ++j) 
            if (tmp[j] == 'H') 
                maps[i] += (1 << j);
    }
    /*for (int i = 0;i < n; ++i) {
        printf("%d\n", maps[i]);    
    }*/
    for (int i = 1;i <= len; ++i) { // 第一行处理 
        if (judge(c[i], maps[1])) 
            dp[1][i][1] = num[c[i]];
    }
    /*for (int i = 0;i < M; ++i) {
        printf("dp[0][%d][0] = %d    can:%d, judge:%d\n", i, dp[0][i][0], can(i), judge(i, maps[0]));
    }*/
    for (int i = 1;i <= len; ++i) {
        if (judge(c[i], maps[2]))
            for (int j = 1;j <= len; ++j) {
                if (judge(c[j], maps[1]) && judge(c[i], c[j]))
                    dp[2][i][j] = max(dp[2][i][j], dp[1][j][1]+num[c[i]]);
            }
    }
    for (int i = 3;i <= n; ++i) { // DP 
        for (int j = 1;j <= len; ++j) {
            if (judge(c[j], maps[i]))
            for (int k = 1;k <= len; ++k) {
                if (judge(c[j], c[k]) && judge(c[k], maps[i-1])) {
                    for (int s = 1;s <= len; ++s) {
                        if (judge(c[s], c[j]) && judge(c[s], c[k]) && judge(c[s], maps[i-2])) {
                            dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][s]+num[c[j]]);
                        }
                    }
                }
            }
        }
    }
    for (int i = 1;i <= len; ++i) { //求解答案 
        for (int j = 1;j <= len; ++j) {
            ans  = max(ans, dp[n][i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}

【题解】POJ 1185,LG P2704【炮兵阵地】

原文：https://www.cnblogs.com/silentEAG/p/10397408.html