关于状态压缩DP以及状态压缩

佚名 6年前 (2019-04-19) 随笔 1398人围观抢沙发百度已收录

首先要明确：状态压缩是利用数字来代表一组序列的方法，从而降低序列访问的复杂度，本质上跟HASH有着差不多的思想，但是其实就是数位运算的一种

定义：集合中共有N个数字，其中每个数字均小于K，能么我们可以用N位K进制数来表示整个集合，能么该数字转化为十进制数字（也就是int or long long），整个状态的表示就变成了一个数字

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

状态的表示i实际上就是利用数字来扩充代表的范围

最典型的一道例题：

USACO 06 corn fields

题目中给定一个N*M的矩阵，其中1代表可操作，0代表不可操作

让你选择其中可操作的点，问给定的矩阵中，两两选定的点不相邻的选择方案数一共有多少种

这是一道非常非常典型的状态压缩DP的问题，阶段可以表示为每一行，其中状态表示当前行中被选定的合法的被操作的点的集合！

其中预处理每行中每种情况的合法性，以及每种情况与每行中能被操作的点的合法性的处理

 1 /* USACO 06 Corn Fields */
 2 
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 
 6 const int MOD=(int)1e9;
 7 
 8 
 9 int dp[13][5000];
10 /* 4096表示为状态压缩 */
11 int Field[13][13];
12 int Fline[13];
13 /* 每行的状态Field的状态 */
14 bool state[5000];
15 int n, m;
16 
17 int main(){
18     cin>>n>>m;
19     for(int i=1;i<=n;i++)
20         for(int j=1;j<=m;j++)
21             cin>>Field[i][j];
22     
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=m;j++)
25             Fline[i]=(Fline[i]<<1)+Field[i][j];
26 
27     int MAX=1<<m;
28     for(int i=0;i<MAX;i++)
29         state[i]=(!(i & (i<<1)) && !(i & (i>>1)));
30     /* for(int i=0;i<MAX;i++)
31         cout<<state[i]<<" ";
32     cout<<endl; */
33     
34     dp[0][0]=1;
35     for(int i=1;i<=n;i++)
36         for(int j=0;j<MAX;j++)
37             if(state[j] && ((j&Fline[i])==j))
38                 for(int k=0;k<MAX;k++)
39                     if((k&j)==0)
40                         dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
41     
42     /* for(int i=1;i<=n;i++){
43         for(int j=0;j<MAX;j++)
44             cout<<dp[i][j]<<" "; */
45         /* cout<<endl;
46     } */
47 
48     int ans=0;
49     for(int i=0;i<MAX;i++) ans=(ans+dp[n][i])%MOD;
50 
51     cout<<ans;
52     
53     return 0;
54 }