状态压缩小结

一般的DP

最长公共子序列 \(f_{i, j}\)表示\(a_{1 \to i}\)和\(b_{1 \to j}\)的最长公共子序列  

背包 \(f_{i, j}\)表示前\(i\)个物品选一些，总体积为\(j\)时的最大价值

但当问题变得很复杂,有\(n\)个不同的属性那么就多开几维,大力出奇迹,就需要状态压缩了

状态压缩

举个🌰(栗子) 

题目

1
2
3
4
n个人玩传球游戏：球可以从任何一个人开始传，每次传给一个还没有接到过球的人，接到球的人继
续传给另一个没有接到过球的人，当所有人都接到过球之后就结束。
任意两个人之间传球都有一定的代价，不同人之间传球的代价可能不相同。求传球游戏结束后的最小总代价。
数据范围：n≤16

用搜索是可以过的,但要记忆化,然而这篇小结是状态压缩

DP做法

设\(n\)个人的编号是\(0,1,\dotsi,n-1\)  

\(f_{S,i}\)表示\(S\)集合中的人已经接过球,且当前球在第\(i\)个人手中的最小总代价

状态转移

算\(f_{S,i}\)时,枚举传球给\(i\)的人\(j\),\(S\)二进制的\(2𝑗\)位必须是1

\(f_{S-2^i,j} + cost_{j,i}\to f_{S,i}\)

代码

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
//初始化
for(int S = 0;S < 1 << N;S++){
    for(int i=0;i<N;i++){
        f[S][i] = 1e9;
    }
}

for(int i=0;i<N;i++){
    f[1 << i][i] = 0;
}
//状态转移
for(int S = 2;S<1<<N;S++){
    for(int i=0;i<N;i++){
        if(S >> i & 1){
            for(int j=0;j<N;j++){
                if(i != j && (S >> j & 1)){
                    f[S][i] = min(f[S][i], f[S ^ 1 << i][j] + cost[j][i]);
                }
            }
        }
    }
}
//答案
int ans = 1e9;
for(int i=0;i<N;i++){
    ans = min(ans, f[(1 << N) - 1][i]);
}

例题

题目 解法 易错点
K.过桥 \(S\)的第\(i\)位为1表示第\(i\)位队员已过桥。
N.送外卖 \(f_{S,i}\): 表示已经访问了集合 \(S\) 中表示的城市，且当前在城市 \(i\) 的最小时间 需要使用\(Floyd\)预处理所有点对之间的最短路径
O.单词游戏 \(f_{S,i}\): 表示当前已经使用的单词集合是 \(S\)，并且最后一个使用的是第 \(i\) 个单词时的最大价值,calc_cost计算重叠部分 许多细节,详见下方
P.玉米地 \(f_{i, S}\) 表示处理到第 \(i\) 行，且第 \(i\) 行状态为 \(S\) 的方案数 \(MODMODMOD\)!!!!!
Q.慢跑小路 要满足“每条边至少走一遍，且起点等于终点”，需要构造一个欧拉回路 需要\(Floyd\)预处理好眼熟,详见下方

部分例题详解

O.单词游戏

需要一个calc_cost计算重叠部分 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int calc_cost(string a, string b) {
    int len_a = a.size();
    int len_b = b.size();
    int max_len = 0;
    int f[12][12] = {};
    for (int i = 0; i < len_a; i++) {
        for (int j = 0; j < len_b; j++) {
            if (a[i] == b[j]) {
                if (i == 0 || j == 0)
                    f[i][j] = 1;
                else
                    f[i][j] = f[i-1][j-1] + 1;
                max_len = max(max_len, f[i][j]);
            }
        }
    }
    return max_len;
}

还要预处理存下来

1
2
3
4
5
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cost[i][j] = calc_cost(dc[i], dc[j]);
    }
}
Q.慢跑小路

需要统计奇度数节点 

1
2
3
4
int p[16], js = 0;
for (int i=1;i<=n;i++)
    if (deg[i]%2 == 1)
        p[js++] = i;

注意结果输出还要加边的总长 printf("%d\n", edge+f[(1<<js)-1]);

还有多组数据的初始化

memset(deg,0,sizeof(deg));

memset(f,0x3f,sizeof(f));

不会有人就错在这里吧 :)

\(THE\) \(END\),作者:\(Hcz\)