状压动态规划 —— ylxmf2005的OI教程

前言

前置芝士:

  1. 位运算
  2. 基础动态规划

状压dp,全称状态压缩动态规划,是利用计算机二进制的性质来描述状态的一种DP方式。很多棋盘问题都运用到了状压。

下面是一些常用的位运算操作:

《状压动态规划 —— ylxmf2005的OI教程》

那么,下面让我们通过一些经典的例题来深入了解一下状压动态规划吧。

$\text{TSP}$ 问题

有 $n$ 个城市(完全图),第 $i$ 个城市到 第 $j$ 个城市的代价为 $d_{i,j}$。求从 $1$ 号城市开始,经过每个城市一次回到 $1$ 号城市的代价。$n \leq 20$。

有四种做法:

  1. 暴力全排列 next_permutation()
  2. 搜索 + 剪枝优化。
  3. 记忆化搜索。
  4. 状压dp。

$dp_{s,last}$ 表示当前在 $last$ 经过了 $s$ 中所有点的代价。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 21;
int d[N][N], f[1 << 20][20], n;
int main(){
    scanf("%d", &n);
    f[1][1] = 0;
    //f(s,now) 表示当前在 now 经过了 s 中所有点的代价。
    for (int S = 2; S < (1 << n); S++) // 枚举所有的从 000010 ~ 111111 
        for (int now = 1; now <= n; now++){//枚举当前在的城市 
            if ((S >> (now - 1)) & 1){ //右数第 now 位是否为 1 
                f[S][now] = INF;
                for (int j = 1; j <= n; j++){//从第 j 个城市走过来 
                    if (S >> (j - 1) & 1) ////右数第 j 位是否为 1 
                        f[S][now] = min(f[S][now], f[S - (1 << (now - 1))][j] + d[now][j]);
                }
            }
        }
    int ans = INF;
    for (int i = 1; i <= n; i++){
        ans = min(ans, f[(1 << n) - 1][i] + d[1][i]);
    }
    printf("%d\n", ans);
    return 0;
}

Corn Fields

Preface

这道好题的题解质量不高吧,我看了好几篇才懂,为了给后人参考一下,于是写了一篇这道题最详细的题解。大家只要认真看就能看懂吧。

Solution

注意题目条件:左右不相邻,上下不相邻,土地肥沃。

设 $dp_{i,j}$ 表示在前 $i$ 行中(包括 $i$ )且 第 $i$ 行状态为 $j$ 的最大方案数。我们的 $i$ 是行,$j$ 是列的状态。10 的意义与题目相同。我们先不看转移方程,因为状压 dp 几乎都不难在方程上。

用二进制数存储数据也是模板了,就不细讲了。每次右移后右边多出个 0,然后加上去。

for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int a; scanf("%d", &a);
            f[i] = (F[i] << 1) + a[i][j];  //储存地图的方法 
        }
    }

先考虑解决左右不相邻。我们对于一个状态,如何知道它是否有相邻的两个 1 呢?这也是本文章最难的一点了。上代码:

for (int i = 0; i < (1 << n); i++) 
        g[i] = (!(i & (i << 1))) && (!(i & (i >> 1)));

模拟一下:对于一个二进制数,假设为 110 即为 0110,左移后为 1100,与运算后为 0100 即为 $4$。对其右移后为 0110,与运算后是 0110 为 $6$, 因为 $4$ 和 $6$ 非运算 后都是 $0$,所以就有两个连续的 $1$。

对于一个二进制数 0001,左移后为 0010,与运算后结果为 $0$,进行右移后为 0000,与运算后还为 $0$。表达式的值也为 $1$ 了。

你可以那么理解:如果有两个连续的 1,那么右移之后至少有一个 1 在同一位置上。左移同理。

右移前: 11
右移后:  11

那么我们就解决了左右不相邻的问题。上下不相邻呢?如果两个位都为 1 与运算后才为 1。我们只要保证 状态 $j_0$ 与 上一行的状态 $j$ 进行与操作之后还不等于 $j_0$ 即可。

土地肥沃也很好解决,只要在枚举的第 $i$ 列的状态 $j$ 中第 $x$ 位是 1,那么我们存的地图 $f_i$ 的第 $i$ 位必须也是 1。你会发现这个用与运算就可以了。

(j & f[i]) == j

那么该说如何转移了,不要忘记判断枚举的状态 $k$ 是否合法哦。统计答案时枚举最后一行的状态即可。

$dp_{i,j}=(dp_{i,j}+dp_{i-1, k}) \ mod \ p$。

Code

#include <bits/stdc++.h> 
using namespace std;
const int p = 100000000, N = (1 << 12) + 12;
int n, m, a[20][20], f[20], dp[20][N];    
bool book[N];
int main() {
    scanf("%d %d", &m, &n); 
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            int a; scanf("%d", &a);
            f[i] = (f[i] << 1) + a;  //储存地图的方法 
        }
    for (int i = 0; i < (1 << n); i++) 
        book[i] = (!(i & (i << 1))) && (!(i & (i >> 1)));//最重要的操作。
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++)  //行 
        for (int j = 0; j < (1 << n); j++)  //状态 
            if (book[j] && ((j & f[i]) == j)) //没有左右相邻并且土地肥沃 
                for (int k = 0; k < (1 << n); k++)  //上一行状态 
                    if ((k & j) == 0) 
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % p;
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) //统计答案 
        ans = (ans + dp[m][i]) % p;
    printf("%d\n", ans);
    return 0;
}

SDOI2009学校食堂

Solution

显然,$(A_i | A_{i+1} )−(A+i \& A_{i+1} ) = A_i \text{^} A _{i+1}$。

令 $dp_{i,j,k}$为 第 $1$ 个人到第 $i-1$ 个人已经打完饭,第 $i$ 个人情况不确定,他和他后面七个人总共八个人的打饭状态为 $j$($1$ 为打饭,$0$ 为没有打饭),且当前最后一个打完饭的人的编号为 $i + k$ 的情况下,所用的最少时间。由于最后一个打完饭的可能在 $i$ 的前面,所以$-8 \leq k \leq 7$。我们需要对 $k$ 加上一个 $8$。

如果当前枚举到了 $i$,当 $i$ 打完饭了(注意:这里 $i$ 打完饭时间是不确定的,所以最后一个打完饭的不一定是 $i$),那么他后面的人是不受限制的,直接转移即可:

dp[i + 1][j >> 1][k - 1] = min(dp[i + 1][j][k - 1], dp[i][j][k]);//j >> 1 能将第 i 个人 “出队”。因为 i 加上了 1,为了让 k 不变,k 要减去 1。

如果当前枚举到了 $i$,当 $i$ 没打完饭的时候。最多能够忍受后面 $B_i$ 个人比他先吃到饭。我们不能直接转移到 $i + 1$了。我们此时用 $x$ 来枚举下一个状态,因为下一个状态不能改变当前已经打饭的人,所以要用与运算判断是否合法。$0 \leq x \leq 7$。

dp[i][j | (1 << x)][x] = min(dp[i][j][k] + time(i + k, i+  x), dp[i][j | (1 << x)][x]); // j | (1 << x) 就是将 (1<<x) 更新到 j 上,j 状态原来打过饭的不用动,新的状态打过饭的要更新了。

你认为这样就行了?不!下面是这道题的难点了:我们的这个转移需要考虑忍耐度,第 $i$ 个人后面的人不是都可以打饭的。需要一个变量 $r$,表示当前为止没打饭的人的忍受范围的最小值(不是忍耐度,忍受范围是指能忍受在其之前打饭的最大位置)。对于任何一个人,如果 $i + x > r$,就不用考虑了。

最后的答案在 $dp_{n + 1,0,k}$ 。$-8 \leq k \leq 0$。因为我们第 $n$ 个人必须打完饭,所以是 $n + 1$。

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1000 + 10;
int t[N], b[N];
int dp[N][1 << 8][21];
int main(){
    int T; scanf("%d", &T);
    while (T--){
        int n; scanf("%d", &n);
        memset(dp, INF, sizeof(dp)); dp[1][0][7] = 0;
        for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &b[i]);
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < (1 << 8); j++)
                for (int k = -8; k <= 7; k++)
                if(dp[i][j][k + 8] != INF){
                    if(j & 1) dp[i + 1][j >> 1][k + 7] = min(dp[i + 1][j][k + 7], dp[i][j][k + 8]);
                    else{
                        int r = INF;
                        for (int x = 0; x <= 8; x++)
                            if(!((j >> x) & 1)){
                                if(i + x > r) break;
                                r = min(r, i + x + b[i + x]);
                                dp[i][j | (1 << x)][x + 8] = 
                                min(dp[i][j][k + 8] + (i + k ? (t[i + k] ^ t[i + x]) : 0), 
                                dp[i][j | (1 << x)][x + 8]);
                            }
                    } 
                }   
        int ans = INF;
        for (int i = 0; i <= 8; i++)
            ans = min(ans, dp[n + 1][0][i]);
        printf("%d\n", ans);
    } 
    return 0;
} 

© 2019 ylxmf2005
转载请联系作者

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据