Bỏ qua

DP nén trạng thái

Giới thiệu

DP trạng thái nén là một dạng của quy hoạch động, bằng cách chuyển tập hợp trạng thái thành số nguyên để ghi lại trong trạng thái DP nhằm thực hiện chuyển trạng thái.

Để đạt được độ phức tạp thời gian thấp hơn, thường cần tìm trạng thái có số lượng nhỏ hơn. Phần lớn bài toán sẽ sử dụng trạng thái nhị phân, dùng số nhị phân \(n\) bit để biểu diễn \(n\) trạng thái độc lập hai giá trị.

Sử dụng trạng thái nén thường liên quan đến thao tác bit, xem thêm về thao tác bit tại trang Toán tử bit.

Bài mẫu 1

「SCOI2005」Không xâm phạm lẫn nhau

Trên bàn cờ \(N\times N\) đặt \(K\) quân vua (\(1 \leq N \leq 9, 1 \leq K \leq N \times N\)), sao cho chúng không tấn công lẫn nhau, hỏi có bao nhiêu cách đặt quân.

Quân vua có thể tấn công 8 ô xung quanh nó (trên, dưới, trái, phải, và 4 ô chéo).

Giải thích

Gọi \(f(i,j,l)\) là số cách hợp lệ khi đã xét \(i\) hàng, trạng thái hàng \(i\) là \(j\), và đã đặt \(l\) quân vua trên bàn cờ.

Với trạng thái \(j\), ta dùng số nguyên nhị phân \(sit(j)\) để biểu diễn cách đặt quân vua, bit \(0\) là không đặt, bit \(1\) là có đặt; \(sta(j)\) là số quân vua trong trạng thái đó, tức là số bit \(1\) trong \(sit(j)\). Ví dụ, trạng thái như hình dưới có thể biểu diễn bằng \(100101\) (bit thấp bên trái), \(sit(j)=100101_{(2)}=37, sta(j)=3\).

Gọi trạng thái hàng hiện tại là \(j\), trạng thái hàng trước là \(x\), ta có phương trình chuyển trạng thái: \(f(i,j,l) = \sum f(i-1,x,l-sta(j))\).

Khi xét trạng thái \(x\) của hàng trước, cần đảm bảo không xung đột với trạng thái \(j\) của hàng hiện tại, liệt kê tất cả \(x\) hợp lệ để chuyển trạng thái:

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

Cài đặt

Mã tham khảo 
 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;
}

Bài mẫu 2

[POI2004] PRZ

Có \(n\) người cần qua cầu, người thứ \(i\) nặng \(w_i\), thời gian qua cầu là \(t_i\). Những người này sẽ chia thành nhiều nhóm, chỉ khi một nhóm qua xong thì nhóm khác mới được qua. Cầu chịu tải tối đa \(W\), hỏi thời gian ngắn nhất để tất cả qua cầu.

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

Giải thích

Dùng \(S\) để biểu diễn một tập con người, \(t(S)\) là thời gian lâu nhất của nhóm \(S\), \(w(S)\) là tổng trọng lượng nhóm \(S\), \(f(S)\) là thời gian ngắn nhất để tất cả \(S\) qua cầu:

\[ \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} \]

Lưu ý không nên liệt kê tập con rồi kiểm tra, mà nên dùng liệt kê tập con, độ phức tạp \(O(3^n)\).

Cài đặt

Mã tham khảo 
 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
#include <iostream>
#include <limits>
#include <vector>
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;
}

Bài tập

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply