状压DP入门详解

（最近做到了状压dp的题目，自己不会，于是学习了一手）

1.位运算（基础）

2.常用的计算方法

一、取出x的第i位：y = ( x>> ( i-1 ) ) & 1

二、将x的第i位取反：x = x ^ ( 1<< ( i-1 ) )

三、将x的第i位变为1：x = x | ( 1<< ( i-1 ) )

四、将x的第i位变成0：x = x & ~（ 1<< ( i-1 ) ）

五、将x最靠右的1变成0：x = x & (x-1)

六、取出最靠右的1：y=x&(-x)

七、把最靠右的0变成1: x | = (x-1)

3.状压dp

何为状压dp，顾名思义就是： 状态压缩+动态规划 。既然是dp那么最为重要的就是找到状态转移方程然后转移就行。不同的在于状压dp利用二进制把状态记录成二进制数。

具体的做法就看后面的例题慢慢体会吧QWQ

例1、关灯问题

这道题目是一个状压的引入和理解，没有涉及dp。

题目链接：
关灯问题

分析：考虑状态压缩，可以把灯的开和关视作1和0，则用一串01串（二进制）表示这一串灯的一个总的状态。
因为这个01串是而进制，所以他们所对应的10进制数最大不会超过（2<<10）-1=1023
也就是说最多有1023种状态，所以当然是可行的。

现在你会发现一点，就是状态压缩只适用于小数据的范围，因为这个二进制数的长度超过64，unsigned long long都存不下啦。

那么这题就可以直接广搜暴利解决，利用之前的计算方法，开灯（1）就是把对应的那一位0变成1：x|=1<<(i-1),如果本身是1的话当然没有任何影响。
同理，关灯（-1）的话就是把对应的那一位1变成0：x=x&~(1<<(i-1)),当然如果本身是0 ，也没有影响啦。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000][1000];
int dp[10000],vis[10000];
queue<int>q;
int main()
{
   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    int siz=0;
    for(int i=1;i<=n;i++) siz=siz<<1|1;
    vis[siz]=1;
    q.push(siz);
    int flag=0;
    while(!q.empty())
    {
   
        int now=q.front();
        q.pop();
        int ans=now;
        for(int i=1;i<=m;i++)
        {
   
            now=ans;
            for(int j=1;j<=n;j++)
            {
   
                if(a[i][j]==-1)
                    now=now|(1<<(j-1));
                else if(a[i][j]==1)
                    now=now&~(1<<(j-1));
            }
            if(vis[now]==0)
            {
   
                q.push(now);
                dp[now]=dp[ans]+1;
                vis[now]=1;
                if(now==0)
                {
   
                    flag=1;
                    printf("%d\n",dp[0]);
                    break;
                }
            }
        }
    }
    if(flag==0) printf("-1\n");
    system("pause");
    return 0;
}
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

例2、玉米田Corn Fields

题目链接：
Corn Fields

分析：
我们可以用1表示种了草，用0表示没有种草，所以每一行的状态都可以描述出来。
n和m的大小为12。故每一行的二进制状态就是2的12次方，也就是4000左右。每一行的每个状态我们都可以用上一行的满足条件的状态转移过来。

问题是怎么判断状态合不合法：

1、同一行有没有相邻的土地种植了草？
直接左移一格（或右移一格）与原状态求交集，为空集则合法。

2、有没有把草种植在贫瘠的土壤上？
把原有土地的状态表示出来，0为贫瘠，1为肥沃，存下每一行的土地状态。将该状态与这一行的土地状态求一下交集，如果等于原状态，则合法。

3、上下两行之间有两格土地连一起怎么办？
在dp状态转移时候，需要枚举上一行的状态，这个时候再进行判断。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e8;
int m,n;//m行n列
int a[14][14],f[14],an
1
2
3
4