狀壓dp

狀態壓縮 dp，英文稱 bitmask dp，使用二進位來表示狀態，來達到類似暴力枚舉的效果

枚舉子集的子集

code

for (int mask = 0; mask < (1 << n); mask++) {
    // 給一個 mask，枚舉他的所有子集合
    for (int S = mask; S; S = (S - 1) & mask) {
        // TODO
    }
}

題目

Atcoder DP Contest O - Matching

有 \(n\) 個男生和女生，第 \(i\) 個男生與第 \(j\) 的女生是否能配對取決於 \(a_{i,j}=\{ 0, 1 \}\)。問有幾種方法能產生 \(n\) 組配對

\(1\le n\le 21\)

思路

可以依照 1, 2, ..., n 的順序讓男生配對，女生則用枚舉 mask

dp(S) = 目前已將男生 [1, |S|] 與女生的集合 S 配對

轉移 dp(S) = dp(S ^ (1 << i)) | a[|S|][i] == 1

code

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

const int INF = 0x3f3f3f3f;
const int M = 1e9 + 7;
const int maxn = 21;
int n;
int a[maxn][maxn];
int dp[1 << maxn];

signed main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    dp[0] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        int now = __builtin_popcount(mask) - 1; 
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i) && a[now][i])) {
                dp[mask] += dp[mask ^ (1 << i)];
                dp[mask] %= M;
            }
        }
    }
    cout << dp[(1 << n) - 1];
}

CSES - Elevator Rides

有 \(n\) 個人，第 \(i\) 個人的重量為 \(w_i\)。給 \(x\)，每次可以移除一個重量和 \(\le x\) 的集合，問最少移除幾次才能將 \(n\) 個人都移除

\(n\le 20, 1\le w_i \le x \le 10^9\)

思路

如果枚舉子集的子集會需要 3^n，TLE

令 dp(S) 為 S 內的人都已經移除的最小次數，f(S) 在移除次數為 dp(S) 下，最後一次移除的最小重量和為多少

dp(S) = dp(S ^ (1 << i)) + (f(S ^ (1 << i)) + w[i] > x)

• f(S ^ (1 << i)) + w[i] > x

  • dp(S) = dp(S ^ (1 << i)) + 1

  • f(S) = f(S ^ (1 << i)) + w[i] - x

• f(S ^ (1 << i)) + w[i] <= x

  • dp(S) = dp(S ^ (1 << i))

  • f(S) = f(S ^ (1 << i)) + w[i]

code

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

const int INF = 2e18;
const int MAXN = 1 << 22;
int n, x;
int w[MAXN], dp[MAXN], t[MAXN];

signed main() {
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    dp[0] = 1;
    t[0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        dp[mask] = INF;
        t[mask] = INF;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int S = mask ^ (1 << i);
                if (w[i] + t[S] <= x) {
                    if (dp[S] < dp[mask] || (dp[S] == dp[mask] && t[S] + w[i] < t[mask])) {
                        t[mask] = t[S] + w[i];
                        dp[mask] = dp[S];
                    }
                } else {
                    if (dp[S] + 1 < dp[mask] || (dp[S] + 1 == dp[mask] && t[S] + w[i] < t[mask])) {
                        t[mask] = w[i];
                        dp[mask] = dp[S] + 1;
                    }
                }
            }
        }
    }
    cout << dp[(1 << n) - 1] << "\n";
}

TIOJ 1418 . 交大都是雷

有 3n 個人，給定倆倆之間若在同組的罰分。問將以 3 個為一組，分成 n 組的最少總罰分

\(1\le n\le 7\)

思路

每次枚舉 mask 裡面的 3 個元素 i, j, k 做轉移，而 i 其實只要枚舉一次就好，因為他無論如何都要配對，早晚不是問題

注意: 需要使用 Top down，因為 Bottom up 會跑到很多沒用的狀態

code

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

int n, v[22][22];
string s;
int dp[1 << 22];

int cost(int a, int b, int c) {
    int ret = v[a][b] + v[a][c] + v[b][c];
    return ret;
}

int solve(int mask) {
    if (dp[mask] > -1) return dp[mask];
    if (!mask) return 0;
    int mn = 1e9;
    for (int i = 0; i < n; i++) {
        if (!((1 << i) & mask)) continue;
        for (int j = i + 1; j < n; j++) {
            if (!((1 << j) & mask)) continue;
            for (int k = j + 1; k < n; k++) {
                if (!((1 << k) & mask)) continue;
                mn = min(mn, solve(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)) + cost(i, j, k));
            }
        }
        break;
    }
    return dp[mask] = mn;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> v[i][j];
            }
        }
        for (int i = 0; i < (1 << n); i++) {
            dp[i] = -1;
        }
        cout << solve((1 << n) - 1) << "\n";
    }
}

TIOJ 1014. 打地鼠

有 \(n\) 個地鼠，分別在點 \(1\) 到 \(n\)。地鼠 \(i\) 每 \(t_i\) 秒會出現一次，玩家從 \(0\) 出發，每秒可以移動一格，問打完所有地鼠所需的最少秒數

\(n \leq 16\)

思路

dp(S, i) = 打完集合 S 內的地鼠，目前在位置 i

dp(S, i) = dp(j, S ^ (1 << i)) + cost(j, i)

cost(j, i) 實則是要將 dp(S, i) 設為 dp(j, S ^ (1 << i)) + |i - j| 下一次 t[i] 出現的時候，所以我們可以列出

dp(S, i) = ceil(dp(j, S ^ (1 << i)) + |i - j|, t[i]) * t[i]

code

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

const int INF = (1LL << 60);
int dp[(1 << 16)][17], t[17];

int iceil(int a, int b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    memset(dp, 0x3f, sizeof(dp));

    dp[0][0] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i) == 0) continue;
            for (int j = 0; j < n; j++) {
                int time = dp[mask ^ (1 << i)][j] + abs(j - i);
                dp[mask][i] = min(dp[mask][i], iceil(time, t[i]) * t[i]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    cout << ans << '\n';
}

LeetCode 698. Partition to K Equal Sum Subsets

給一個長度為 n 的序列 a，問能不能分成 k 組，使得每組的總和相同

\(1\le k\le n\le 16, 0\le a_i\le 10^4\)

思路

先看 target = a[0], ..., a[n - 1] 是否符合 target % k == 0，不是的話直接 return，是的話再將 target /= k

dp(S) = S 是否能分成好幾組，每組的 sum 都是 target

dp(S) = dp(S ^ U) | (sum[U] == target)

複雜度 O(3^n)，其實我們在預處理 sum[U] 可以做到 O(2^n)，就是利用

sum[U] = sum[U - lowbit(U)] + a[__builtin_ctz(lowbit(mask))]

code

#define lowbit(x) (x & (-x))
class Solution {
   public:
    bool canPartitionKSubsets(vector<int>& a, int k) {
        int n = a.size();
        int tar = 0;
        for (auto ele : a) tar += ele;
        if (tar % k) return 0;
        tar /= k;
        vector<int> sum(1 << n);
        for (int mask = 1; mask < (1 << n); mask++) {
            int idx = __builtin_ctz(lowbit(mask));
            sum[mask] = sum[mask - lowbit(mask)] + a[idx];
        }
        vector<int> dp(1 << n);
        dp[0] = true;
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int s = mask; s > 0; s = (s - 1) & mask) {
                if (sum[s] == tar && dp[mask ^ s]) {
                    dp[mask] = true;
                    break;
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

CF 1886 E - I Wanna be the Team Leader

有 \(m\) 個 projects，難度分別為 \(b_1, \ldots ,b_m\)，有 \(n\) 個人，抗壓程度分別為 \(a_1, \ldots ,a_n\)。現在需要分組，滿足以下條件 :

• 使每個 project 至少有一個人做
• 每個人至多負責一個 project
• 令負責第 \(j\) 個 project 的人有 \(k\) 個，則這些 \(a_i\) 須滿足 \(a_i\le\frac{b_j}{k}\)

\(n\le 2\times 10^5, m\le 20,1\le a_i, b_i\le 10^9\)

思路

考慮將序列 \(a\) 大到小 sort，每個 \(b_i\) 挑的就會是一個 prefix，因為如果不是一個 prefix，那對於最後面的那格我們只在意前面選的數量，因此可將倒數第二格與前面的某個的 \(b_i\) swap，還可以讓其他 \(b_i\) 挑的 \(a_i\) 的最小值變大，一直這樣做就會變好幾個連續區段。那問題就可以用 bitmask dp 解決，\(dp[S]\) 代表 \(S\) 目前 prefix 選到哪裡可使 \(S\) 內的 \(b_i\) 都滿足條件，轉移的話枚舉不在 \(S\) 內的 \(j\)，看 \(j\) 要延伸到哪裡，我們令 \(j\) 支配的區段為 \([dp[S]+1,dp[S\cup j]]\)，\(dp[S\cup j]=nxt(j,dp[S])\)。\(nxt(j,i)\) 代表 \(b_j\) 從 \(i\) 開始往右選最少選到哪裡即可使 \(b_j\) 滿足條件。

Graph coloring problem

最小點著色、 k 點著色，都是 NP-complete 問題

四色定理

平面圖一定可以四著色，P 問題，有著 O(N²) 演算法，但不一定可以三著色。詳見 Wiki 或 演算法筆記

k-Vertex Coloring

給一張 \(n\) 點 \(m\) 邊無向圖，問是否能 \(k\)-coloring，使每條邊兩端的顏色都不同

思路

k = 2

二分圖判斷

---

k = 3

\(O(m\times 2^n)\) 列舉第一種獨立集，剩下的二分圖

---

k = 4

令 \(dp(S)=S\) 是否可以 2-colors 上色，建表複雜度 \(O(m\times 2^n)\)。列舉 \(S\) 使得 \(dp(S)\) 跟 \(dp(V\setminus S)\) 都要是 true

Minimum Vertex Coloring / Chromatic Number

給一張 \(n\) 點 \(m\) 邊無向圖，問最少塗幾種顏色可使每條邊兩端的顏色都不同

思路

令 \(dp(S)=S\) 最少多少 coloring，轉移式

\[ dp(S)=\min\limits_{T\in S} \{ dp(S \setminus T) + 1 \} \]

其中 \(T\) 要是獨立集，複雜度 \(O(3^n)\)