状压入门

状压入门

状压dp是dp中比较难的一种，从状压开始，后面的dp就开始区分职业选手与普通程序员了。本篇主要讲解状压dp的主要思路与部分入门题目。

什么是状压？

首先需要明确什么是状态压缩。

状压指的是用二进制的位来描述状态，并使用位运算来处理关系的方式。

例如有一排灯，可以用1，0来描述开关灯，用位运算来进行区间修改与单点修改。

状压的思路可通过以下入门题目进一步了解。

P1896 [SCOI2005] 互不侵犯

原题链接：P1896 [SCOI2005] 互不侵犯

首先用sit数组来模拟出一行所有可能的状态，再用数组dp[n][cnt][sum]进行枚举，其中n代表一行，cnt代表这一行的排布情况，sum代表所使用的国王数，易得转移方程为

$$
dp[i][j][s]+=dp[i-1][k][s-sum[j]]
$$

其中i表示第i行，j表示第i行的排布，k表示第i-1行的排布，s表示已使用国王的数量。

代码如下：

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int sit[2000];
int sum1[2000];
int cnt;
int n,m;
ll dp[10][2000][100];
void dfs(int con,int sum,int node){
	if(node>=n){
		cnt++;
		sit[cnt]=con;
		sum1[cnt]=sum;
		return;
	}
	dfs(con,sum,node+1);
	dfs(con+(1<<node),sum+1,node+2);//排除两个连续的点均为king的情况
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	dfs(0,0,0);//dfs出每一行可能的情况
	for(int i=1;i<=cnt;i++)dp[1][i][sum1[i]]=1;//第一行的情况为1
	for(int i=2;i<=n;i++){
		for(int j=1;j<=cnt;j++){//对i行枚举
			for(int k=1;k<=cnt;k++){//对i-1行枚举
				if(sit[j]&sit[k])continue;
				if((sit[j]<<1)&sit[k])continue;
				if((sit[k]<<1)&sit[j])continue;//排除特殊情况
				for(int s=m;s>=sum1[j];s--)dp[i][j][s]+=dp[i-1][k][s-sum1[j]];//dp转移
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=cnt;i++)ans+=dp[n][i][m];
	cout<<ans;
}

P1879 [USACO06NOV] Corn Fields G

题目链接：P1879 [USACO06NOV] Corn Fields G

和上一题的思路类似，先用一个q数组记录每一行的情况，再用一个pd数组表示状态是否存在(即是否存在左右矛盾)。在验证某个状态是否存在的时候可以取(j&q[i])是否为j来验证。

使用dp[i][j]表示第i行j种状态下的种植方案数，则转移方程为：

$$
dp[i][j]=(dp[i-1][k]+dp[i][j])mod(MOD)
$$

代码如下：

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,m;
ll MOD=100000000;
bool pd[1<<20];//存储一行可能的情况
int arr[14][14];
int dp[14][1<<20];
int q[14];//存储每一行的初始情况
void dp1(){
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<(1<<n);j++){
			if(pd[j]&&((j&q[i])==j)){//检测此状态是否存在
				for(int k=0;k<(1<<n);k++){
					if((k&j)==0)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;//核心步骤
				}
			}
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>arr[i][j];
			q[i]=(q[i]<<1)+arr[i][j];
		}
	}
        for(int i=0;i<(1<<n);i++){
		pd[i]=(!(i&(i<<1)))&&(!(i&(i>>1)));//枚举每行所有可能的情况
	}
	dp1();
	int ans=0;
	for(int i=0;i<(1<<n);i++)ans=(dp[m][i]+ans)%MOD;
	cout<<ans;
}

P2704 [NOI2001] 炮兵阵地

题目链接：P2704 [NOI2001] 炮兵阵地

这道题的处理非常巧妙，先用一个arr数组记录每一行的状态（H为1，P为0），再用sum数组储存每种情况1的数量。在检测状态 j 是否与 arr[i] 矛盾时，只需要检测 j&arr[i] 是否为0即可，若为0则说明可以存放，且sum[j] 即为这一行所存放的炮兵阵地的数量。dp方程即为：

$$
dp[i][j][k]=max(dp[[i][j][k],dp[l][i][k-1]+sum[j])
$$

其中 i 表示处理的一行， j 表示前一行，l 表示前前行，k 表示行序。

其中有不少细节需要注意：

  1. 由于是三行三行的枚举，故需要先预处理第一，二行的情况，并存放在dp数组中，再从第三行开始枚举。数据加强后专门对只有1行的情况进行了补充。
  2. 需要开滚动数组，不然会爆。
  3. 排除当前行可用 i&(i<<1) 与 i&(i<<2)，这样左二与右二都可以排除。

代码如下：

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
60
61
62
63
64
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,m;
int arr[150];
int dp[1<<10][1<<10][3];//滚动数组
int sum[1<<10];
int ans;
int get1(int x){//获取一行中“1”的数量
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
    char index;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>index;
            arr[i]<<=1;
            arr[i]+=((index=='H')?1:0);//H为1，P为0
        }
        for(int i=0;i<(1<<m);i++){
            sum[i]=get1(i);//统计每一种情况中“1”的个数
        }
    }
    //想想，为什么明明统计的是“1”的个数，sum却表示的是一行中炮兵阵地的个数？
    for(int i=0;i<(1<<m);i++){
        if(!((i&arr[0])||i&(i<<1)||(i&(i<<2)))){
            dp[i][0][0]=sum[i];
        }
        for(int j=0;j<(1<<m);j++){
            if(!(i&j||i&(i<<1)||j&(j<<1)||i&(i<<2)||j&(j<<2)||i&arr[0]||j&arr[1])){
                dp[i][j][1]=sum[i]+sum[j];//预处理第二行
            }
        }
    }
    for(int k=2;k<n;k++){
        for(int i=0;i<(1<<m);i++){
            if(i&arr[k-1]||i&(i<<1)||i&(i<<2))continue;//枚举上一行
            for(int j=0;j<(1<<m);j++){
                if(i&j||j&arr[k]||j&(j<<1)||j&(j<<2))continue;//枚举当前行
                for(int l=0;l<(1<<m);l++){
                    if(l&i||l&j||l&arr[k-2]||l&(l<<1)||l&(l<<2))continue;//枚举上上行
                    dp[i][j][k%3]=max(dp[i][j][k%3],dp[l][i][(k-1)%3]+sum[j]);//状态转移
                }
            }
        }
    }
    for(int i=0;i<(1<<m);i++){
        for(int j=0;j<(1<<m);j++){
            ans=max(ans,dp[i][j][(n-1)%3]);//计算总和
        }
    }
    cout<<ans;
}
算法
#算法 #洛谷
状压入门
https://shepherdzzx.github.io/状压入门/
Author
Shepherdz
Posted on
June 14, 2024
Licensed under