定义

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

引入

题目描述

互不侵犯

在 N*N 的棋盘里面放 K 个国王（1 <= N <= 9, 1 <= K <= N * N），使他们互不攻击，共有多少种摆放方案。

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

思路分析

设 dp(i,j,l) 表示前 i 行，第 i 行的状态为 j，且棋盘上已经放置 l 个国王时的合法方案数。

对于编号为 j 的状态，我们用二进制整数 state(j) 表示国王的放置情况，state(j) 的某个二进制位为 0 表示对应位置不放国王，为 1 表示在对应位置上放置国王；用 stateCount(j) 表示该状态的国王个数，即二进制数 state(j) 中 1 的个数。例如，如下图所示的状态可用二进制数 100101 来表示（棋盘左边对应二进制低位），则有 state(j)=100101, stateCount(j)=3。

设当前行的状态为 j，上一行的状态为 k，在保证当前行和上一行不冲突的前提下，枚举所有可能的 k 进行转移，转移方程：

f(i,j,l)=∑f(i−1,k,l−sta(j))f(i,j,l) = \sum f(i-1,k,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
40
41
int state[2005];
int stateCount[2005];
long long dp[10][2005][105];
int stateCnt = 0;
int N, K;

void dfs(int s, int num, int cur) {
    if (cur >= N) {
        state[++stateCnt] = s;
        stateCount[stateCnt] = num;
        return;
    }
    dfs(s, num, cur + 1);
    dfs(s + (1 << cur), num + 1, cur + 2);
}

inline bool isCompatible(int i, int j) {
    if (state[i] & state[j]) return false;
    if ((state[i] << 1) & state[j]) return false;
    if (state[i] & (state[j] << 1)) return false;
    return true;
}

int main() {
    cin >> N >> K;
    dfs(0, 0, 0);
    for (int i = 1; i <= stateCnt; i++) dp[1][i][stateCount[i]] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= stateCnt; j++) {
            for (int k = 1; k <= stateCnt; k++) {
                if (!isCompatible(j, k)) continue;
                for (int l = stateCount[j]; l <= K; l++) {
                    dp[i][j][l] += dp[i - 1][k][l - stateCount[j]];
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= stateCnt; i++) ans += dp[N][i][K];
    cout << ans << endl;
}

典型例题

最短Hamilton路径

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
const int maxN = 1 << 20;
int dp[maxN][25];
int g[25][25];

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> g[i][j];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 2; i < (1 << N); i++) {
        for (int j = 0; j < N; j++) {
            if ((i >> j) & 1) {
                for (int k = 0; k < N; k++) {
                    if ((i >> k) & 1 && k != j) {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + g[k][j]);
                    }
                }
            }
        }
    }
    cout << dp[(1 << N) - 1][N - 1];
}

关灯问题II

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
int a[105][15];
int vis[1 << 10];

struct node {
    int state;
    int step;
    node(int state, int step) : state(state), step(step) {}
};

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];
    queue<node> q;
    q.emplace((1 << N) - 1, 0);
    vis[(1 << N) - 1] = 1;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (cur.state == 0) {
            cout << cur.step << endl;
            return 0;
        }
        for (int i = 0; i < M; i++) {
            int s = cur.state;
            for (int j = 0; j < N; j++) {
                if (a[i][j] == 1 && s & (1 << j)) s ^= (1 << j);
                else if (a[i][j] == -1 && !(s & (1 << j))) s |= (1 << j);
            }
            if (!vis[s]) {
                q.emplace(s, cur.step + 1);
                vis[s] = 1;
            }
        }
    }
    cout << -1 << endl;
}

炮兵阵地

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
40
41
42
const int N = 110, M = 10, S = 1 << M;

int n, m;
int g[N];
int f[2][S][S];

vector<int> state;
vector<int> stateCnt;

bool check(int s) {
    for (int i = 0; i < m; i++)
        if (s >> i & 1 && ((s >> (i + 1) & 1) || (s >> (i + 2) & 1)))
            return false;
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char ch;
            cin >> ch;
            if (ch == 'H') g[i] |= 1 << j;
        }
    for (int i = 0; i < 1 << m; i++) {
        if (check(i)) {
            state.emplace_back(i);
            stateCnt.emplace_back(__builtin_popcount(i));
        }
    }

    for (int i = 0; i < n + 2; i++)
        for (int j = 0; j < state.size(); j++)
            for (int k = 0; k < state.size(); k++)
                for (int u = 0; u < state.size(); u++) {
                    int a = state[j], b = state[k], c = state[u];
                    if (a & b || a & c || b & c) continue;
                    if (g[i] & c) continue;
                    f[i & 1][k][u] = max(f[i & 1][k][u], f[i - 1 & 1][j][k] + stateCnt[u]);
                }
    cout << f[n + 1 & 1][0][0] << endl;
}

Corn Fields G

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
40
41
const int maxN = 12, maxS = 1 << maxN;
const int mod = 1e8;
int g[maxN];
int dp[maxN][maxS];
vector<int> state;

int M, N;

void dfs(int s, int cur) {
    if (cur >= N) {
        state.emplace_back(s);
        return;
    }
    dfs(s, cur + 1);
    dfs(s | (1 << cur), cur + 2);
}

int main() {
    cin >> M >> N;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++) {
            int num;
            cin >> num;
            num = 1 - num;
            g[i] |= num << j;
        }
    dfs(0, 0);
    for (int i : state) if ((i & g[0]) == 0) dp[0][i] = 1;
    for (int i = 1; i < M; i++) {
        for (int j = 0; j < state.size(); j++) {
            for (int k = 0; k < state.size(); k++) {
                int u = state[j], v = state[k];
                if (v & u || v & g[i]) continue;
                dp[i][v] = (dp[i][v] + dp[i - 1][u]) % mod;
            }
        }
    }
    int ans = 0;
    for (int i : state) ans = (ans + dp[M - 1][i]) % mod;
    cout << ans << endl;
}

中国象棋

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
using LL = long long;

const int mod = 9999973;

LL dp[105][105][105];

inline LL C(int m) {
    return (m * (m - 1) / 2) % mod;
}

int main() {
    int n, m;
    cin >> n >> m;
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m - j; k++) {
                dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
                if (j >= 1) dp[i][j][k] += dp[i - 1][j - 1][k] * (m - (j - 1) - k);
                if (k >= 1) dp[i][j][k] += dp[i - 1][j + 1][k - 1] * (j + 1);
                if (j >= 2) dp[i][j][k] += dp[i - 1][j - 2][k] * C(m - (j - 2) - k);
                if (k >= 1) dp[i][j][k] += dp[i - 1][j][k - 1] * j % mod * (m - j - (k - 1));
                if (k >= 2) dp[i][j][k] += dp[i - 1][j + 2][k - 2] * C(j + 2) % mod;
                dp[i][j][k] %= mod;
            }
        }
    }
    LL ans = 0;
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= m - i; j++)
            ans += dp[n][i][j] % mod;
    cout << ans % mod << endl;
}

一双木棋 chess

1