AIOJ

Introduction

Bitmask DP is a form of dynamic programming that transforms a set of states into an integer and records it in the DP state to perform state transitions.

To achieve lower time complexity, it is usually necessary to find a state representation with fewer states. In most problems, binary states are used: an $n$ -bit binary number represents $n$ independent binary states.

State compression usually involves bitwise operations. For basic bitwise operations, see the Bitwise Operations page.

Example 1

「SCOI2005」Non-attacking Kings

Place $K$ kings on an $N\times N$ chessboard ( $1 \leq N \leq 9, 1 \leq K \leq N \times N$ ) so that they do not attack each other. How many placements are there?

A king can attack the one nearby square in each of the eight directions—up, down, left, right, upper left, lower left, upper right, and lower right—for a total of $8$ squares.

Explanation

Let $f(i,j,l)$ denote the number of valid arrangements after the first $i$ rows, where the state of row $i$ is $j$ and $l$ kings have already been placed on the chessboard.

For state number $j$ , we use the binary integer $sit(j)$ to represent the placement of kings. A binary digit of $sit(j)$ equal to $0$ means that no king is placed at this position, while $1$ means that a king is placed there. Let $sta(j)$ denote the number of kings in the state, that is, the number of $1$ bits in the binary number $sit(j)$ . For example, the state shown below can be represented by the binary number $100101$ (the left side of the chessboard corresponds to the low-order binary bit), so $sit(j)=100101_{(2)}=37, sta(j)=3$ .

Let the current row's state be $j$ and the previous row's state be $x$ . The following state transition equation is obtained: $f(i,j,l) = \sum f(i-1,x,l-sta(j))$ .

Let $x$ be the state number of the previous row. Under this condition that the current and previous rows do not conflict, enumerate every possible $x$ for the transition. The transition equation is:

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

Implementation

Reference code

#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) {  // There is a new valid state
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // Do not place a king at position cur
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // Place a king at position cur; adjacent positions can no longer contain kings
}

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);  // Precompute all valid states for one row
  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;  // Exclude invalid transitions
        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];  // Accumulate the answer
  cout << ans << endl;
  return 0;
}

Example 2

[POI2004] PRZ

There are $n$ people who need to cross a bridge. The weight of person $i$ is $w_i$ , and their crossing time is $t_i$ . These people are divided into several groups when crossing the bridge. A remaining group can cross only after everyone in one group has crossed. The bridge's maximum load is $W$ . What is the shortest time for all these people to cross the bridge?

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

Explanation

Let $S$ denote a subset of the set of all people, let $t(S)$ denote the longest crossing time among the people in $S$ , let $w(S)$ denote the total weight of all people in $S$ , and let $f(S)$ denote the shortest time for all people in $S$ to cross the bridge. Then:

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

Note that instead of directly enumerating sets and checking whether they are subsets, submask enumeration should be used, giving a time complexity of $O(3^n)$ .

Implementation

Reference code

#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;
}

Bitmask DP

Introduction

Example 1

Explanation

Implementation

Example 2

Explanation

Implementation

Exercises