跳转至

狀壓 DP

定義

狀壓 DP 是動態規劃的一種，通過將狀態壓縮為整數來達到優化轉移的目的。

例題 1

「SCOI2005」互不侵犯

在 \(N\times N\) 的棋盤裏面放 \(K\) 個國王（\(1 \leq N \leq 9, 1 \leq K \leq N \times N\)），使他們互不攻擊，共有多少種擺放方案。

國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共 \(8\) 個格子。

解釋

設 \(f(i,j,l)\) 表示前 \(i\) 行，第 \(i\) 行的狀態為 \(j\)，且棋盤上已經放置 \(l\) 個國王時的合法方案數。

對於編號為 \(j\) 的狀態，我們用二進制整數 \(sit(j)\) 表示國王的放置情況，\(sit(j)\) 的某個二進制位為 \(0\) 表示對應位置不放國王，為 \(1\) 表示在對應位置上放置國王；用 \(sta(j)\) 表示該狀態的國王個數，即二進制數 \(sit(j)\) 中 \(1\) 的個數。例如，如下圖所示的狀態可用二進制數 \(100101\) 來表示（棋盤左邊對應二進制低位），則有 \(sit(j)=100101_{(2)}=37, sta(j)=3\)。

設當前行的狀態為 \(j\)，上一行的狀態為 \(x\)，可以得到下面的狀態轉移方程：\(f(i,j,l) = \sum f(i-1,x,l-sta(j))\)。

設上一行的狀態編號為 \(x\)，在保證當前行和上一行不衝突的前提下，枚舉所有可能的 \(x\) 進行轉移，轉移方程：

\[ f(i,j,l) = \sum f(i-1,x,l-sta(j)) \]

實現

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;

void dfs(int x, int num, int cur) {
  if (cur >= n) {  // 有新的合法状态
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // cur位置不放国王
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // cur位置放国王，与它相邻的位置不能再放国王
}

bool compatible(int j, int x) {
  if (sit[j] & sit[x]) return false;
  if ((sit[j] << 1) & sit[x]) return false;
  if (sit[j] & (sit[x] << 1)) return false;
  return true;
}

int main() {
  cin >> n >> k;
  dfs(0, 0, 0);  // 先预处理一行的所有合法状态
  for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
      for (int x = 1; x <= cnt; x++) {
        if (!compatible(j, x)) continue;  // 排除不合法转移
        for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
      }
  long long ans = 0;
  for (int i = 1; i <= cnt; i++) ans += f[n][i][k];  // 累加答案
  cout << ans << endl;
  return 0;
}

例題 2

[POI2004] PRZ

有 \(n\) 個人需要過橋，第 \(i\) 的人的重量為 \(w_i\)，過橋用時為 \(t_i\). 這些人過橋時會分成若干組，只有在某一組的所有人全部過橋後，其餘的組才能過橋。橋最大承重為 \(W\)，問這些人全部過橋的最短時間。

\(100\le W \le 400\)，\(1\le n\le 16\)，\(1\le t_i\le 50\)，\(10\le w_i\le 100\).

解釋

我們用 \(S\) 表示所有人構成集合的一個子集，設 \(t(S)\) 表示 \(S\) 中人的最長過橋時間，\(w(S)\) 表示 \(S\) 中所有人的總重量，\(f(S)\) 表示 \(S\) 中所有人全部過橋的最短時間，則：

\[ \begin{cases} f(\varnothing)=0,\\ f(S)=\min\limits_{T\subseteq S;~w(T)\leq W}\left\{t(T)+f(S\setminus T)\right\}. \end{cases} \]

需要注意的是這裏不能直接枚舉集合再判斷是否為子集，而應使用 子集枚舉，從而使時間複雜度為 \(O(3^n)\).

實現

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int W, n;
  cin >> W >> n;
  const int S = (1 << n) - 1;
  vector<int> ts(S + 1), ws(S + 1);
  for (int j = 0, t, w; j < n; ++j) {
    cin >> t >> w;
    for (int i = 0; i <= S; ++i)
      if (i & (1 << j)) {
        ts[i] = max(ts[i], t);
        ws[i] += w;
      }
  }
  vector<int> dp(S + 1, numeric_limits<int>::max() / 2);
  for (int i = 0; i <= S; ++i) {
    if (ws[i] <= W) dp[i] = ts[i];
    for (int j = i; j; j = i & (j - 1))
      if (ws[i ^ j] <= W) dp[i] = min(dp[i], dp[j] + ts[i ^ j]);
  }
  cout << dp[S] << '\n';
  return 0;
}

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用