[洛谷P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/solution/P2704) 这道题是状态压缩DP。 ~~~cpp #include using namespace std; int n, m, cnt; int mp[105], sta[200], sum[200]; int dp[105][200][200]; bool check(int x) { return !(x & (x 1)) && !(x & (x >> 2)); } void init() { for (int i = 0; i n >> m; for (int i = 0; i > s; for (int j = 0; j < m; j++) { if (s[j] == 'H') mp[i] |= (1 = 2 && (sta[p] & mp[i-2])) continue; if (sta[k] & sta[p]) continue; if (sta[j] & sta[p]) continue; if (dp[i-1][k][p] == -1) continue; dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][p] + sum[j]); } } } } int ans = 0; for (int j = 0; j < cnt; j++) for (int k = 0; k < cnt; k++) ans = max(ans, dp[n-1][j][k]); cout

洛谷P2704 [NOI2001] 炮兵阵地题解

Yichen

洛谷P2704 [NOI2001] 炮兵阵地

这道题是状态压缩DP。

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt;
int mp[105], sta[200], sum[200];
int dp[105][200][200]; 

bool check(int x) {
    return !(x & (x << 1)) && !(x & (x << 2)) &&
           !(x & (x >> 1)) && !(x & (x >> 2));
}

void init() {
    for (int i = 0; i < (1 << m); i++) {
        if (check(i)) {
            sta[cnt] = i;
            sum[cnt] = __builtin_popcount(i);
			//__builtin_popcount函数用于计算一个整数的二进制表示中1的个数（豪用） 
            cnt++;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == 'H') mp[i] |= (1 << (m - j - 1));
        }
    }

    init();

    memset(dp, -1, sizeof(dp));
    for (int j = 0; j < cnt; j++) {
        if (sta[j] & mp[0]) continue;
        dp[0][j][0] = sum[j];
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < cnt; j++) { 
            if (sta[j] & mp[i]) continue;
            for (int k = 0; k < cnt; k++) { 
                if (sta[k] & mp[i-1]) continue;
                if (sta[j] & sta[k]) continue;
                for (int p = 0; p < cnt; p++) { 
                    if (i >= 2 && (sta[p] & mp[i-2])) continue;
                    if (sta[k] & sta[p]) continue;
                    if (sta[j] & sta[p]) continue;
                    if (dp[i-1][k][p] == -1) continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][p] + sum[j]);
                }
            }
        }
    }

    int ans = 0;
    for (int j = 0; j < cnt; j++)
        for (int k = 0; k < cnt; k++)
            ans = max(ans, dp[n-1][j][k]);
    cout << ans << endl;
    return 0;
}