状压dp

ACM

状态压缩：将集合的状态用一个数字表示，这个数字的每一位是0或者1，表示着一个元素的两种状态。
此处应该介绍一下位运算和性质(脑补一下？)
几大类状压dp:

  • TSP问题
  • 密铺问题(轮廓线法)
  • 插头dp
  • 传统的状压dp问题
    后面的两类问题并不会。

题目

TSP问题

题意

  • 从0开始，经过图中所有的点有且仅有一次，最终回到原点
  • 这个图是完全图
  • 问最小的路径距离

题解

  • 状态设计: dp[i][state]:到达i这个点，状态为state的最短路,state的二进制每一位为1表示访问过了，0表示没有被访问过
  • 状态转移：
    if(state|(1<<j) == 0) dp[j][state|(1<<j)] = min(dp[j][state|(1<<j)], dp[i][state]+dis[i][j]);
  • 边界：dp[0][0] = 0;
  • 结果: dp[0][(1<<n)-1]

AC代码

注意min()被重写了。

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
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include<cstring>
using namespace std;
int dis[16][16];
int n;
int dp[17][1<<16];
int min(int x, int y){
    if(x == -1) return y;
    if(y == -1) return x;
    if(x<=y) return x;
    else return y;
}
void solve(){
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int state=0; state<(1<<n); state++){
        for(int i=0; i<n; i++){
            if(dp[i][state] != -1){
                for(int j=0; j<n; j++){
                    if(dp[j][state|(1<<j) == 0]){//j点没有被访问过，注意中括号的位置！
                        dp[j][state|(1<<j)] = min(dp[i][state]+dis[i][j],
                                                  dp[j][state|(1<<j)]);
                    }
                }
            }
        }
    }
    cout<<dp[0][(1<<n)-1]<<endl;
}
int main()
{
    while(cin>>n&&n){
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                cin>>dis[i][j];
            }
        }
        n++;
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                }
            }
        }
        solve();
    }
    return 0;
}

问题

Mondriaan’s Dream

题意

  • 在n*m的格子中铺满1*2或者2*1的格子
  • 一共有多少种铺设方案

题解

  • 状态设计: dp[i][state]:第i行在前面i-1行全部铺满的情况下的状态state(因为第i-1行铺设的时候可能会竖着铺影响到第i行，把所有被第i-1行影响到的格子记录成state)

  • 状态转移:
    ①若第j列被第i-1行影响了，那么跳这一列在第j+1列铺
    ②竖着铺，影响到第i+1行的第j列的格子(改变nex).
    ③横着铺，若第j+1列是空着的，那么直接跳到第j+2列铺，否则在第j列只能竖着铺。（横着铺不影响第i+1行的状态，因此不需要改变nex）

  • 边界: dp[0][0] = 1;（个人感觉边界的起始点设置的很神奇，空即是有还是无?）

  • 结果: dp[n][0],（行从0开始到n-1）state == 0表示第n+1行上面没有铺设任何的格子。

AC代码

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 <cstdio>
#include <cstring>
using namespace std;
int h, w;
const int maxn = 11;
long long dp[maxn+3][1<<maxn];
void dfs(int column, int row, int state, int nex){
    //nex表示下一行的状态
    if(column == w){
        dp[row+1][nex] += dp[row][state];
        return ;
    }
    //这个一开始想错了emmmmm，注意位运算表示的意义
    // 区分>0和 == 1 的差别！
    if(((1<<column)&state) > 0)dfs(column+1, row, state, nex);
    else{
      dfs(column+1, row, state, (nex|(1<<column)));
      if(column+1<w&&(state&(1<<(column+1))) == 0)
            dfs(column+2, row, state, nex);
    }
}
int main()
{
    while(scanf("%d%d", &h, &w)&&h+w!=0){
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;//初始条件很有意思，它的实际意义呢？
        for(int i=0; i<h; i++){
            for(int state = 0; state<(1<<w); state++){
                if(dp[i][state]){
                    dfs(0, i, state, 0);
                }
            }
        }
        printf("%lld\n", dp[h][0]);
    }
    return 0;
}

未解决的问题

插头dp,轮廓线题目推荐
看艾教的ppt,很多都不会emmmm被菜醒。

本文标题:状压dp

文章作者:Babydragon

发布时间:2017-11-04, 17:31:16

最后更新:2018-03-23, 13:35:04

原始链接:http://baolintian.github.io/2017/11/04/状压dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. AC代码
  2. 2. 问题
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. AC代码
  3. 3. 未解决的问题
{{ live2d() }}