动态规划之状态压缩

状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度,但速度比搜索快,其思想非常值得借鉴。

为了更好的理解状压dp,首先介绍位运算相关的知识。

1.’&’符号,x&y,会将两个十进制数在二进制下进行与运算,然后返回其十进制下的值。例如3(11)&2(10)=2(10)。

2.’|’符号,x|y,会将两个十进制数在二进制下进行或运算,然后返回其十进制下的值。例如3(11)|2(10)=3(11)。

3.’^’符号,x^y,会将两个十进制数在二进制下进行异或运算,然后返回其十进制下的值。例如3(11)^2(10)=1(01)。

4.’<<’符号,左移操作,x<<2,将x在二进制下的每一位向左移动两位,最右边用0填充,x<<2相当于让x乘以4。相应的,’>>’是右移操作,x>>1相当于给x/2,去掉x二进制下的最有一位。

这四种运算在状压dp中有着广泛的应用,常见的应用如下:

1.判断一个数字x二进制下第i位是不是等于1。

方法:if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

将1左移i-1位,相当于制造了一个只有第i位上是1,其他位上都是0的二进制数。然后与x做与运算,如果结果>0,说明x第i位上是1,反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法:x = x | ( 1<<(i-1) )

证明方法与1类似,此处不再重复证明。

3.把一个数字二进制下最靠右的第一个1去掉。

方法:x=x&(x-1)

感兴趣的读者可以自行证明。

下面来一道状态压缩的例题(然而弱鸡的我例题都做了好久。。。)

https://www.luogu.org/problemnew/show/1896

整理一下思路。

所谓的状态压缩,我个人认为是用时间换方便,将所有情况汇集在一个数里,本来是要用多个维度才能表示的情况换作一个维度。

可能一道题有多种状态,而每种状态都需要我们去讨论,而如果为每个状态都单独开一个数组来存储状态,那就GG了,根本存不下。

所以我们就把10进制的转换为二进制来存储,二进制每一位0,1都可以表示选择与否,一个二进制数就可以完成对多种状态的存储。

然而对与时间复杂度却是指数级的,所以对于数据范围大的,这个就无法使用了。

来波代码

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 long long f[100][900][1000];//f[行数][国王个数][状态];
 5 int way[105];
 6 int num[105];
 7 int find(int n,int all)
 8 {
 9     int j=0;
10     for(int i=0;i<=all;i++)
11     {
12         if((i&(i<<1))==0&&(i&(i>>1))==0)
13         {            
14             j++;
15             way[j]=i;
16             int x=i;
17             int nn=0;
18             while(x>0)
19             {
20                 nn++;
21                 x=x-(x&(-x));
22                 //每执行一次这项操作,会消去x作为二进制数时最右端的一个1。 
23             }
24             num[j]=nn;
25         }
26     }
27     return j;
28 }
29 bool search(int s2,int s1)//判断两种状态是否冲突。
30 {
31     if((s2&(s1<<1))==0&&(s1&(s2<<1))==0&&(s1&s2)==0)
32     return true;
33     else
34     return false;
35 }
36 int main()
37 {
38     int n,k1;
39     scanf("%d%d",&n,&k1);
40     int all=1<<n;
41     all--;//总共存在的状态数
42     int nway=find(n,all);//找出一行中不会冲突的最多方案的个数
43     for(int i=1;i<=nway;i++)
44     {
45         f[1][num[i]][way[i]]=1;
46     }
47     for(int i=2;i<=n;i++)//行数
48     for(int j=1;j<=nway;j++)//上一行状态 
49     for(int t=1;t<=nway;t++)//这一行状态 
50     {
51         if(search(way[j],way[t]))
52         {
53             for(int g=num[t];g<=k1;g++)
54             {
55                 f[i][g][way[t]]+=f[i-1][g-num[t]][way[j]];
56                 //状态转移方程。
57             }
58         }
59     }
60     long long tot=0ll;//记住要使用long long型不然就像我一样交了半天都不对。
61     for(int i=1;i<=nway;i++)
62     {
63         tot+=f[n][k1][way[i]];
64     }
65     printf("%lld",tot);
66     return 0;
67 } 
原文地址:https://www.cnblogs.com/genius777/p/8470411.html