状压DP

使用状压DP的原因

我们知道状态压缩，顾名思义，就是需要考虑的状态非常多，我们如果用平常的思想去表示状态，那是非常不现实的，在时间和空间上都不允许，我们使用某种方法，以最小的代价表示某种状态。 那么，这通常是用进制来表示状态的，而选择几进制则根据要求使用的对象的点的状态有几种。一般来说，只有0和1，我们则是用二进制来表示，当然也有其他进制的题，在例题中会列举，需要我们灵活变通，主要谈二进制。

那么如何用二进制表示状态呢？我们发现，二进制上是按位分的，那么我们每一位可以看成一个点，而点上的取值则为该点的状态或者选择。例如00001001这个状态则表示第一个点和第四个点状态为1，其余的点状态为0。所以按照这种思想，能抽象的表示出一个很复杂的状态，实现了时间和空间的优化。

状压DP的适用条件

状态压缩其实是有适用环境的：

  1. 状态需要有一定的状态单元。 即一个状态应该是保存一个集合，其中的元素值对应着0或1，例如我们常见的棋盘，我们可以用0或1来表示棋子的放置状态。而整个集合即是一个01串，即二进制数，我们通常用十进制表示。那么我们再进行状态转移或者判断的时候，需要先将十进制转化为二进制，再将二进制转化为十进制。
  2. 题目中限制的集合大小不会超过20。 这是最显著的特征，为什么呢？我们知道如果用二进制表示状态，那么集合大小为20的二进制状态有2^{20} - 1已经达到1e7的数量级了。
  3. 具有动态规划的特性。 对于动态规划，一般都是要求最优化某个值，具有最优子结构的性质。同时也需要满足状态转移的特性，而不是前一个状态毫无关系的。

适用环境总结：

  1. 二进制
  2. 集合/状态大小受限（比如不会大于int类型能表示的最大数）
  3. 满足动态规划特性

状压DP的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
int maxn = 1 << n;//总状态数。
//枚举已有的集合数。按照状态转移的顺序，一般从小编号到大编号。

for(int i = 1; i <= m; ++ i){
    //枚举当前集合中的状态。
    for(int j = 0; j < maxn; ++ j){
        //判断当前集合是否处于合法状态，通常我们需用一个数组提前处理好。如g数组;
        if(当前状态是否合格){
            for(int k = 0; k < maxn; ++ k){
                //枚举上一个集合的状态。
                if(上一个集合的状态是否合格 + 上一个集合的状态和当前状态的集合是否产生了冲突){
                    列写状态转移方程。
                }
            }
        }
    }
}


例题

USACO06NOV Corn Fields G

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入格式

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式

一个整数，即牧场分配总方案数除以100,000,000的余数。

输入

1
2
3
2 3
1 1 1
0 1 0

输出

1
9

思路：

我们先作出规定，定义n代表的是行，m代表的是列。那么牧场大小就是n × m。我们看到数据范围,n , m都特别小，同时所求为方案数，这很符合状压DP的适用条件。那么对于每一行，我们就可以看成一个未知集合，而集合的大小自然就是列m。对于每一个单元，其取值范围为0 , 1，而1代表放置奶牛，0代表不放置奶牛，所以我们自然可以用二进制表示，那么状态总数就是( 1 < < m ) − 1。

  1. 对于每一个状态，我们需要判断是否合格，而其中明确不能选择两块相邻的土地，在集合内，即相邻位不能全为1，所以我们可以预处理g数组，处理方式即为:g[i] = !(i & (i << 1))（这里的i的取值从0到所有的状态）；
  2. 同样，我们还应该知晓土地的状况，因为毕竟只有土地肥沃才可以放置奶牛，则我们可以通过一个st数组判断，集合与集合之间，我们也需要考虑相邻位不能全为1，所以在枚举上一个集合的状态也需要严格判断。
  3. 对于状态定义，我们可以用f [ i ] [ j ]表示第i行且状态为j的方案数。
  4. 对于状态转移，假设上一行状态为k，则状态转移方程为：f [ i ] [ j ] + = f [ i − 1 ] [ k ]

答案：

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
54
55
56
57
58
59
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 10 + 5,M = 10 + 5;
const int P = 1e8;

int n,m;//n行m列的土地。
int a[N][M],st[N];//a代表土地，st代表每一行的土地状况。
bool g[1 << N];//g得到所有状态中的合法状态。
int f[N][1 << N];//f[i][j]表示的则是第i行且状态为j的方案数，是由上一行转移过来的，所以我们定义上一行的状态为k。
//则状态转移方程为f[i][j] += f[i - 1][k];//其中j和k必须满足条件。
void solve(){
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            scanf("%d", &a[i][j]);
        }
    }
    //得到每一行的土地状况。
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            st[i] = (st[i] << 1) + a[i][j];
        }
    }
    //得到所有状态中的合法状态。
    int maxn = 1 << m;//总状态。
    f[0][0] = 1;//初始化，这种也算一种。
    for(int i = 0; i < maxn; ++ i){
        g[i] = !( i & (i << 1));//由于不能相邻，所以我们左移判断是否符合条件。 
    }
    for(int i = 1; i <= n; ++ i){
        //枚举每一行。
        for(int j = 0; j < maxn; ++ j){
            //枚举每一行的状态，判断此状态是否符合条件。1.不能相邻。2.是全部状态的子集。
            if(g[j] && (j & st[i]) == j){
                //如果符合条件。则我们去判断上一行是否符合。
                for(int k = 0; k < maxn; ++ k){
                    //枚举上一行状态。注意，这里我们无需判断上一行状态是否存在，因为不存在即为0.
                    //只需要判断j和k是否存在相邻草地。
                    if(!(j & k)){
                        f[i][j] = (f[i][j] + f[i - 1][k]) % P;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int j = 0; j < maxn; ++ j){
        ans = (ans + f[n][j]) % P;
    }
    printf("%d\n", ans);
    solve();
    return 0;
}

糖果

【问题描述】
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将M种口味编号1~M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是K颗一包整包出售。
幸好糖果包装上注明了其中K颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定N包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果
【输入格式】
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K个整数 T1,T2,….Tκ，代表一包糖果的口味。
【输出格式】
一个整数表示答案。如果小明无法品尝所有口味，输出-1。

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
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();
    int m=sc.nextInt();
    int k=sc.nextInt();
    int[][] a = new int[n][k];
    int[] sta = new int[n];
    int[] dp = new int[1<<k];
    Arrays.fill(dp, -1);
    dp[0]=0;	// 动规数组只有dp[0]为0，其余全部初始化-1
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            a[i][j] = sc.nextInt(); // 读取数据
            /* 此处用sta[i]做了k次或赋值，解释如下。 */
            /* 对于数据a[i][j]，意味第i个包裹中的第j块糖果的种类 */
            /* 比如a[i][j]是第4类糖果，那么1<<(a[i][j]-1)的值为二进制的1000，也就是第四类糖果被选中。 */
            /* 当sta[i]做了k次或赋值后，sta[i]的二进制上会有若干个1，表示第i个包裹中有哪些类别的糖果。 */
            sta[i] |= 1 << (a[i][j] - 1);           	
        }
        /* 这里说明一下dp数组的含义 */
        /* dp[l] = k，表示要想获得l的二进制表示的所有糖果种类，至少要选取k个包裹。 */
        /* 由于我们刚刚初始化sta数组，那么这里表示的含义就是对于每一个包裹，要想获得这个包裹里的所有糖果种类，需要1个包裹。 */
        dp[sta[i]] = 1;
    }
    /* 接下来就是动规得出答案了 */
    for(int i=1; i<=n; i++) { // 依次考虑每一个包裹，获取包裹后会对dp有什么影响
        for(int j=0; j<(1<<m); j++) { // 在考虑包裹i时，对所有已经存在的状态j都做分析，看包裹i是否对状态j有所影响
            if (dp[j] == -1) continue; // 状态j不存在，考虑下一个
            /* 分两种情况 */
            /* 状态j存在，但拿到包裹i后，状态j|sta[i]不存在，更新之 */
            /* 状态j存在，拿到包裹i后的状态也存在，但在状态j下拿到包裹i，比之前的代价更小，更新之 */
            if (dp[j | sta[i]] == -1 || dp[j] + 1 < dp[j|sta[i]]) {
                dp[j | sta[i]] = dp[j] + 1;
            }
        }
    }
    System.out.println(dp[(1 << m) - 1]); // 最后输出的是要拿到所有糖果种类需要的最少包裹数
}