前言

不知道为什么越是接近网络赛就越是静不下心来，可能也是因为开学了吧，QAQ，有一说一还是暑假比较适合训练。第一场网络赛，特意选了一个属于我们队的“风水宝地”（其实是我们去的早获得了优先选择权），但是好像并没有什么用，读题读巨慢，还被签到卡了2h（大概，有点不记得了），最后开j，队友推公式写了一手，发现错了，准备调的时候，队友讨论了一下，说结论假了QAQ。感觉不能放任自己这样下去，在dalao的建议下，决定写写DP，又想到第一场网络赛的I要状压DP，那就状压！！！

定义

状态压缩动态规划，顾名思义就是： 状态压缩 + 动态规划，即通过状态压缩来达到优化的目的

引入

Hamilton问题

题目描述

给定一张 \(n\) 个点的带权无向图，点从 \(0 \sim n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短 Hamilton 路径。
Hamilton 路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。

题目分析

一眼看上去，呀！这不就是除了首位以外的全排列嘛！某人（指自己）很容易想到用深搜 + 最优化剪枝，然后某人得到

T了之后某人才开始算时间复杂度（这是不对的！应该在写程序之前就计算好，要不然就会像某人一样，写一个绝对不可能AC的代码），不难发现，时间复杂度为O(n!)，显而易见，这是不可行的。

虽然很难想到(bushi)，但是这题我们可以通过DP，再加上状态压缩的优化来解决，能将复杂度降低到O(\(n^2 * 2^n\))。

1、首先，我们来设计状态，我们可以把走过和没走过i点分别标记为1/0，不妨设dp[][]，第一维表示：当前所有点的状态（是否被走过），第二维表示：当前状态下的终点

2、然后，我们来思考状态转移方程，不难想到dp[11][2] = std::min({dp[10][1] + dis[1][2] , dp[01][0] + dis[0][2]})，在这个基础上，我们用符号来表示就是：dp[s][j] = std::min(dp[s - j][k] + dis[k][j] , dp[s][j]);

3、因为起点是固定的，并且我们要求最短的Hamilton路径，所以我们将dp数组初始化为最大值，dp[1][0] = 0;

分析好了后，我们不难写出代码

 for(int s = 1;s < (1 << n);s ++ ){
    for(int j = 0;j < n;j ++){
        if((s >> j) & 1){//当前集合包含j
            for(int k = 0;k < n;k ++){//s-j包含k
                if ((s ^ (1 << j)) >> k & 1){
                    dp[s][j] = std::min(dp[s][j],dp[s ^ (1  << j)][k] + ans[k][j]);
                }
            }
        }
    }
}

只有当集合包含j时，才存在j为终点；s-j集合包含k，即表示在j没有被走过的集合状态下，集合包含k。状态转移方程表示：j没有被走过的集合状态下，以k为终点的路径，再从k走到j的值，与dp[s][j]原来的值比较，取值其中的小者。

原理

状态dp的应用背景是以集合为状态，用二进制来表示集合中元素的状态。

状压dp的思想主要是：用二进制表示集合的状态，并用二进制的位运算遍历和操作，操作简单并且速度快。

但是需要注意的是，状态压缩只是一种DP处理集合的工具，时间复杂度主要还是取决于dp算法本身，与是否使用状态压缩关系不大。

一些例子

方格取数(1)

Problem Description

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

3
75 15 21 
75 15 28 
34 70 5 

Sample Output

188

Author

ailyanlu

我的代码

#include <bits/stdc++.h>
//#define int long long
int dp[2][(1 << 20) + 1];
int a[21][21];
int tot[(1 << 20) + 1];
int cal(int i , int x){
    int cnt = 1 , res = 0;
    while (x){
        if(x & 1) res += a[i][cnt];
        x /= 2;
        cnt ++;
    }
    return res;
}
signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);
    int n;
    while (std::cin >> n){
        
        for(int i = 0 ; i < 2 ; i ++){
            for(int j = 0 ; j <= (1 << 20) ; j ++){
                dp[i][j] = 0;
            }
        }
        
        for(int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= n ; j ++){
                std::cin >> a[i][j];
            }
        }

        int cnt = 0;
        for(int i = 0 ; i < (1 << n) ; i ++){
            if((i & (i >> 1)) == 0) {//如果i & i >> 1，说明i一定没有相邻的两个1
                tot[++cnt] = i;
            }
        }

        for(int i = 1 ; i <= n ; i ++){//每一行
            for(int j = 1 ; j <= cnt ; j ++){
                int val = cal(i , tot[j]);//算出第i行，取j状态时
                for(int k = 1 ; k <= cnt ; k ++){
                    if(!(tot[j] & tot[k])) {//因为当前行的状态只跟上一行有关，可以用滚动数组优化空间
                        dp[i % 2][k] = std::max(dp[i % 2][k], dp[(i - 1) % 2][j] + val);
                    }
                }
            }
        }
        
        int max = 0;
        for(int i = 0 ; i <= cnt ; i ++){
            max = std::max(max , dp[n % 2][i]);
        }
        std::cout << max << "\n";
    }
    return 0;
}

题目分析

我们可以使用二进制来表示某一行的选择状态，即状态压缩。如果i & (i- 1) == 0，则说明在二进制状态下相邻的位置不会同时为1。在每一行的位置，根据上一行的情况，尝试所有的可能情况，因为空间的限制，我们可以使用滚动数组来进行优化。

[「SCOI2005」互不侵犯] (https://loj.ac/p/2153)

题目描述

在 \(N \times N\) 的棋盘里面放 \(K\) 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 \(8\) 个格子。

输入格式

只有一行，包含两个数 \(N\), \(K\)。

输出格式

所得的方案数。

样例

输入

3 2

输出

16

我的代码

#include <bits/stdc++.h>
#define int long long
int tot[(1 << 10)];
int dp[10][(1 << 10)][100];
int cnt;

int cal(int x){//当前状态能放多少个棋子
    int res = 0;
    while (x){
        if(x & 1) res ++;
        x /= 2;
    }
    return res;
}

void solve(){
    int n , k;
    std::cin >> n >> k;

    for(int i = 0 ; i < (1 << n) ; i ++){//计算在横向满足条件的状态
        if((i & (i >> 1)) == 0) tot[++ cnt] = i;
    }

    int ans = 0;

    for(int i = 1 ; i <= cnt ;i ++){//初始化第一行的状态
        dp[1][i][cal(tot[i])] ++;
    }

    for(int i = 2 ; i <= n ; i ++){//第i行
        for(int j = 1 ; j <= cnt ; j ++){//第i - 1行是j状态时
            for(int p = 1 ; p <= cnt ; p ++){//第i行时p状态
                int val = cal(tot[p]);//p状态能放的棋子数
                //判断在第i - 1行为j状态下，第i行是否能放p状态的棋子
                if((tot[p] & tot[j]) == 0 && (((tot[p] << 1) & tot[j]) == 0) && (((tot[p] >> 1) & tot[j]) == 0)) {
                    for(int l = val ; l <= k ; l ++) {//当第i行为p状态时，放了l个棋子的情况有几种
                        dp[i][p][l] += dp[(i - 1)][j][l - val];
                    }
                }
            }
        }
    }

    for(int i = 1 ; i <= cnt ; i ++){//最后一行为i状态时，棋子数为k的方案数
        ans += dp[n][i][k];
    }
    std::cout << ans << '\n';

}
signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

    int t = 1;
//    std::cin >> t;
    while (t --){
        solve();
    }
    return 0;
}