算法学习笔记15——状压DP 2024.07.27 算法学习笔记

算法学习笔记(15):状压DP

状压DP也就是用到了状态压缩思想的动态规划。

状态压缩通常利用01位来对状态进行概括，位运算的效率高，能把看似N的状态直接变成1（前提是N不大）

动态规划都需要状态转移方程，那么状压思想就从一个角度去把状态用一个值表示，把状态到状态之间的转移变成状压后值的转移。

在网格题中十分常见。

以例题作为思想体现。

互不侵犯（国王问题）

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

题解

对于DP的思想，很容易想到先建立一维用来表示前n行，之后再思考转移时候需要注意的事情，对于第 i 行的考量，需要考虑到 i - 1 行的状态（上行的国王不能攻击到）。所以我们需要在状态转移的时候保存上一行国王状态。此时就用到了状态压缩。

n的数据大小不大，故例如n=10，我们就可以用10个0和1来表示。

此时由于问的是K个国王有多少种摆放方案，因此再增加一个维度k来表示国王的数量。

此时 dp[line][status][kingNum] 成为当前思路建立的状态。（可以空间优化掉line）

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

using i64 = long long;
// dp[i][status][k] 前i行状态为status时，放置了k个国王的方案数
i64 dp[10][1 << 9][92];

int main(){
    i64 n, K;
    cin >> n >> K;
    i64 maxStatus = 1 << n;

    // 初始行的状态和国王数量
    for(int i = 0; i < maxStatus; i++){
        i64 kingCnt = 0;
        bool valid = true;
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                kingCnt++;
                // 判断当前行的国王是否相邻
                if(j > 0 && (i & (1 << (j - 1)))){
                    valid = false;
                    break;
                }
            }
        }
        if(valid && kingCnt <= K) {
            dp[1][i][kingCnt] = 1;
        }
    }

    // 状态转移
    for(int line = 2; line <= n; line++){
        for(int lastStatus = 0; lastStatus < maxStatus; lastStatus++){
            int falseStatus = 0;
            for(int pos = 0; pos < n; pos++){
                if(lastStatus & (1 << pos)){
                    falseStatus |= (1 << pos);
                    if(pos > 0) falseStatus |= (1 << (pos - 1));
                    if(pos < n - 1) falseStatus |= (1 << (pos + 1));
                }
            }

            for(int status = 0; status < maxStatus; status++){
                if(status & falseStatus) continue;
                int kingCnt = 0;
                bool valid = true;
                for(int i = 0; i < n; i++){
                    if(status & (1 << i)){
                        kingCnt++;
                        if(i > 0 && (status & (1 << (i - 1)))){
                            valid = false;
                            break;
                        }
                    }
                }
                if(!valid) continue;

                for(int k = 0; k + kingCnt <= K; k++){
                    dp[line][status][k + kingCnt] += dp[line - 1][lastStatus][k];
                }
            }
        }
    }

    i64 result = 0;
    for(int i = 0; i < maxStatus; i++){
        result += dp[n][i][K];
    }
    cout << result << endl;
}

代码结构过于混乱，之后可以有更好的写法。

Corn Fields G (luogu P1879)

有一块长方形的新牧场，这块牧场被划分成 M 行 N 列 (1≤M≤12,1≤N≤12)，每一格都是一块正方形的土地。 JohnJohn 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 JohnJohn 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

题解

同样，可以用二进制状压状态，而且也只要保存上一行的状态即可，同时这题多了一个限制条件，也就是不能在贫瘠的地方种田。只需要保存贫瘠状态，然后进行and运算，判断这个状态是否合法。

对于不能相邻，(s1 & (s1 << 1))，(s1 & (s1 >> 1))便可以轻松判断。

#include<bits/stdc++.h>using namespace std;
using i64 = long long;
const int MOD = 1e8;

int dp[13][1 << 12] = {};

bool isValid(int s1) {
    if (s1 & (s1 << 1)) return false;
    if (s1 & (s1 >> 1)) return false;
    return true;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> M(n + 1, 0);
    const int maxStatus = (1 << m);

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int tmp;
            cin >> tmp;
            if (tmp == 0) {
                M[i] |= (1 << j);
            }
        }
    }

    for (int status = 0; status < maxStatus; status++) {
        if (isValid(status) && !(M[1] & status)) {
            dp[1][status] = 1;
        }
    }

    for (int i = 2; i <= n; i++) {
        for (int s1 = 0; s1 < maxStatus; s1++) {
            if (!isValid(s1) || (M[i - 1] & s1)) continue;
            for (int s2 = 0; s2 < maxStatus; s2++) {
                if (!isValid(s2) || (M[i] & s2)) continue;
                if (s1 & s2) continue;
                dp[i][s2] = (dp[i][s2] + dp[i - 1][s1]) % MOD;
            }
        }
    }

    int result = 0;
    for (int st = 0; st < maxStatus; st++) {
        result = (result + dp[n][st]) % MOD;
    }
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

P2704 [NOI2001] 炮兵阵地

司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。

一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示）。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围是上下左右四个方向各两格，一共有8格。

题解

本题有两个限制条件，一个限制是地图限制，已经在上面说过了，另一个是攻击限制，不同于国王题，国王题在考虑限制的时候只需要考虑上一行，然而炮兵题的炮兵可以攻击到下面两行，所以在考虑第 i 行的时候必须也要考虑i - 1行和 i - 2 行，状态方程就需要保存两个状态值，分别表示上行和这行。

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

int dp[105][1 << 10][1 << 10];
// 前i行，上行为j，这行为k的最多炮兵数量。

bool isFaildPos(int status){
    if((status << 2) & status) return true;
    if((status << 1) & status) return true;
    if((status >> 2) & status) return true;
    if((status >> 1) & status) return true;

    return false;
}

bool isValid(int status1, int status2, int nowStatus){
    if((status1 & nowStatus) or (status2 & nowStatus)){
        return false;
    }
    return true;
}

int toBanStatus(const string & line){
    int curExp = line.size() - 1;
    int resStatus = 0;
    for(int i = 0; i < line.size(); i++){
        if(line[i] == 'H'){
            resStatus |= (1 << curExp);
        }
        curExp--;
    }
    return resStatus;
}

int countNum(int status){
    int res = 0;
    while(status){
        if(status & 1) res++;
        status >>= 1;
    }
    return res;
}

void solve(){
    int n, m;
    cin >> n >> m;
    const int maxStatus = (1 << m);
    vector<int> M(n + 1);
    M[0] = (1 << 10) - 1;
    for(int i = 1; i <= n;i++){
        string line;
        cin >> line;
        M[i] = toBanStatus(line);
    }
    int maxNum = 0;

    for(int s2 = 0; s2 < maxStatus; s2++){
        if(isFaildPos(s2)) continue;
        if(M[1] & s2) continue;

        dp[1][0][s2] = countNum(s2);
        maxNum = max(dp[1][0][s2], maxNum);
    }

    for(int i = 2; i <= n; i++){
        for(int s1 = 0; s1 < maxStatus; s1++){
            if(s1 & M[i - 2]) continue;
            if(isFaildPos(s1)) continue;
            for(int s2 = 0; s2 < maxStatus; s2++){
                if(s2 & M[i - 1]) continue;
                if(isFaildPos(s2)) continue;
                for(int s3 = 0; s3 < maxStatus; s3++){
                    if(s3 & M[i]) continue;
                    if(isFaildPos(s3)) continue;
                    if(not isValid(s1, s2, s3)) continue;
                    dp[i][s2][s3] = max(dp[i][s2][s3], dp[i - 1][s1][s2] + countNum(s3));
                    maxNum = max(dp[i][s2][s3], maxNum);
                }
            }
        }
    }
    cout << maxNum << endl;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

通过这个代码，可以把判断是否合法的问题转移到外部的函数，不同于国王问题的代码，这个代码更加清晰易懂。（主要在出现问题时能马上发现）

一双木棋 chess（P4363）

落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

状压思想

这里只说明状压思想，不对题目进行解题，意在开拓不同的状压思路。

现在状态压缩需要保存的是整个棋盘的状态，棋盘最大大小为10x10，如何记录这个状态。

通过这个下棋题意，能说明一点，下面的行想要下棋，上一行就必须有棋。可以证明从上往下每一行的棋子是递减的。

所以如果我们知道了有几行的棋子数量是1 1 4 5 1 4，马上就可以判断出实际上是5 4 4 1 1 1，因为必定降序，所以只需要记录数字的出现，有哪些数字即可。而且一共10个数字。

可以用0作为间隔，一共列出m个0，然后一行有x个棋子就在第x个0后面插入一个1，此时的二进制状态记录了0-10每个数的数字数量，并且最多20个位，是一个很独特的思路。

例如5 4 4 1 1 1

实际上是 0 1 1 1 0 0 0 1 1 0 1（前面是最小位）

状压代码

int addOnePos(int status, int pos){
    int newStatus = 0;
    newStatus |= ((status >> pos) << (pos + 1));
    newStatus |= (1 << pos);
    newStatus |= status % (1 << pos);
    return newStatus;
}

int findPos(int status, int num){
    int cnt = 0;
    int pos = 0;
    for(pos = 0; cnt < num; pos++){
        if((status & (1 << pos)) == 0)
            cnt++;
    }
    return pos;
}

int generateStatus(const vector<int> & sta){
    int status = 0;
    for(int num : sta){
        int pos = findPos(status, num);
        status = addOnePos(status, pos);
    }
    return status;
}

void analyzeStatus(int status, vector<int> &result, int &sumP){
    int cnt = 0;
    int pos = 0;
    for(pos = 0; pos <= 21; pos++){
        if((status & (1 << pos)) == 0)
            cnt++;
        else{
            sumP += cnt;
            result.push_back(cnt);
        }
    }
}