#edu2005. 状态压缩与DP

状态压缩与DP

前置知识【位运算】

位运算就是基于整数二进制的运算，计算机内部采用二进制存储数据，位运算速度很快。

基本的位运算共6种，分别是按位与（&）、按位或（∣|）、按位异或（∧\wedge）、按位取反（∼\sim）、左移（<<<<）和右移（>>>>）。

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。

位运算运算规则相关资料很多，这里不再赘述。

强调一下异或运算，异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 a∧b∧b=a a \wedge b \wedge b = a

位运算一般有三种作用:

  1. 根据题目需要进行位运算。

  2. 高效地进行某些运算，代替其他低效的方法,例如 2n2^n 就是 1<<n1<<n 。“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”最好使用位运算，需要注意，用位运算代替其他运算方式在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。

  3. 表示集合的状态。

模拟集合操作：一个数的二进制可以看作一个集合（ 11 表示对应位置的数在集合内，00 表示不在集合内）

操作 集合表示 位运算语句
交集 a∩b a\cap b "a&b"
并集 a∪b a\cup b "a|b"
补集 ā '~a'
差集 a\b(属于a,不属于b的集合) "a & (~b)"
对称差 a∆b "a^b"

注释：对称差(只属于其中一个集合，而不属于另一个集合的元素组成的集合。)

子集遍历：

// 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u)
{
  // s 是 u 的一个非空子集
}

枚举子集的子集

状态压缩中，经常需要枚举“子集的子集”。 枚举 nn 个元素的所有子集的子集，时间复杂度是 O(n3)O(n^3)。

【问题理解】

假设有一个包含 nn 个元素的集合 SS，我们需要枚举所有子集 A⊆SA⊆S ，并对每个子集 AA 再枚举其所有子集 B⊆AB⊆A 。 总时间复杂度由两部分组成：枚举所有子集 A⊆SA⊆S：共有 2n2^n 个子集 。

对每个子集 AA，枚举其所有子集 B⊆AB⊆A：若 ∣A∣=k∣A∣=k ，则有 2k2^k 个子集 BB 。

总操作次数就是：∑k=0n(nk)×2k\sum_{k=0}^n \binom{n}{k} \times 2^k .

根据二项式定理：

$(1+2)^n=\sum_{k=0}^n \binom{n}{k} \times 1^{(n-k)} \times 2^k=\sum_{k=0}^n \binom{n}{k} \times 2^k = 3^n$

伪代码：

for(int s=0;s<(1<<n);s++)
  for(int t=s;t;t=(t-1)&s)  // t 是 s 子集
      //Coding Here

【状态压缩】

二进制状态压缩，实际是指将一个长度为 k 的 bool 数组（表示集合的中元素的状态）用对应的一个 k 位二进制数表示，这个二进制数实际就是一个整数，可以利用位运算对这个整数的任意一位进行操作。

1.	取出整数 n 在二进制表示下的第 k 位 ：（n>>k）&1
2.	对整数 n 在二进制表示下第 k 位赋值 1： n= n|(1<<k)
3.	对整数 n 在二进制表示下第 k 位赋值 0：n= n&(~(1<<k))
4.	对整数 n 在二进制表示下第 k 位取反：  n= n^(1<<k)
5.	取出整数 n 在二进制表示下的第 0~k-1 位（后k位）：n&((1<<k)-1)

状压整数nn如果太大，可以使用STLSTL中bitsetbitset进行状压。

【状压 DPDP 入门】

一般的动态规划利用两三个关键信息描述清楚问题（定义状态），描述的问题都具有无后效性和最优重叠子结构，使得问题具有阶段性，然后根据已知信息依次对各个阶段进行决策，也就是状态转移。

然而有时候一般的状态描述难以满足无后效性原则，或者保存的信息不足以决策，很多元素的状态都会影响到决策，这些元素的状态都需要被考虑到。为描述清楚每个元素的状态，开一个数组来存储，也就是状态用数组来表示，空间显然不够，可以对这多个元素的状态进行压缩存储，压缩存储后就是一个整数，用这个整数表示各个元素的状态，这就是状态压缩，阶段间需要进行决策，这是动态规划，两块结合起来就是状态压缩 DPDP。

【经典问题】

旅行商问题(即 TSPTSP 问题，TravelingSalesmanProblemTraveling Salesman Problem) 一个 n(≤15)n(\leq15) 个点的带权完全图（不是完全图也可以，没有边的当做无穷大），求权和最小的经过每个点恰好一次的封闭回路。

这个问题也是 HamiltonHamilton 回路问题，很容易想到本题的一种暴力算法，就是枚举 nn 个点的全排列，计算路径长度取最小值，时间复杂度为 O(n∗n!)O(n*n!) ，n=15n=15 会超时。

这个问题已经被证明是一个 NPNP 完全问题，那么对于这样一类无多项式算法的问题，是否还存在比暴力搜索高效一些的算法了？

我们发现只要知道哪些点已经被遍历过而遍历过的点具体顺序对以后决策时没有影响的，那就可以用一个整数 ss 表示集合中点的状态，设当前处在位置 ii 上，就可以描述清楚这个问题。

f[s][i]f[s][i] 表示当前所有点的状态是 ss （二进制下 00 表示未走，11 表示已走），处在第 ii 个位置上，走过的最小路径权和。

状态转移方程：

f[s∣(1<<j)][j]=min{f[s][i]+dist[i][j]}f[s|(1<<j)][j]=min\{ f[s][i]+dist[i][j] \}

其中 j！=ij！=i，jj 不在 ss 集合中（即 ss 的第 jj 位为 00 ）,从 ii 走到 jj。

Answer=min(f[(1<<n)−1][Answer=min(f[(1<<n)-1][终点]+dist[]+dist[起点][][终点])]) ,注意起点和终点不确定，所以需要求最小值。

算法复杂度为 O(2n∗n2)O(2^n*n^2) ，虽然是指数级算法，但是对于 n=15n=15 规模来说已经比暴力高效很多了。

我们将这类以集合内所有元素状态信息作为状态描述的动态规划叫做状态压缩 DpDp。基于状态压缩的动态规划问题通常具有以下两个特点：

  1. 数据规模的某一维或几维非常小。
  2. 描述问题涉及到集合中所有元素的状态。
  3. 具有动态规划的基本性质：最优重叠子结构和无后效性。

例1. P1433 吃奶酪

题意：房间里放着 nn 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0)(0,0) 点处。

【解析】

题目中不需要回到 (0,0)(0,0) 处, TSPTSP 模板题。

状态转移方程：

$f[s|(1<<j)][j]=min(f[s|(1<<j)][j],f[s][i]+dis(x[i],y[i],x[j],y[j]))$

参考代码：

#include<bits/stdc++.h>
using namespace std;
double f[1<<15][15];
int n;
double x[15],y[15];
double dis(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>x[i]>>y[i];
	
	memset(f,127,sizeof(f));
	
	for(int i=0;i<n;i++)
		f[1<<i][i]=dis(0,0,x[i],y[i]);
	
	for(int s=0;s<(1<<n);s++)
		for(int i=0;i<n;i++)
			if(s&(1<<i))
			for(int j=0;j<n;j++)
				if((s&(1<<j))==0)
					f[s|(1<<j)][j]=min(f[s|(1<<j)][j],f[s][i]+dis(x[i],y[i],x[j],y[j]));
	double ans=1e18;
	for(int i=0;i<n;i++)ans=min(ans,f[(1<<n)-1][i]);
	printf("%0.2lf",ans);
	return 0;
}

类似问题 P1171售货员的难题，本质就是“哈密顿回路”，最终结果只需要增加一条边就构成回路了。

例2. 平面密铺问题

P10975 Mondriaan's Dream 来源于 poj2411

题意： 求把 N×MN×M 的棋盘分割成若干个 1×21×2 的的长方形，有多少种方案。

例如当 N=2N=2，M=4M=4 时，共有 55 种方案。当 N=2N=2，M=3M=3 时，共有 33 种方案。

如下图所示：

ss

【思路点拨】

对于任意一种方案，考虑以某一行为界，把整个棋盘分成两部分，上半部分最后一行中，有的地方会竖着一个 1∗21*2 的长方形，决定了下一行必须补全该长方形，也就是对下一行有影响，而其余地方对下一行没有影响。

我们可以把“行号”作为 DPDP 的“阶段”，本行中竖着的 1∗21*2（会对下一行有影响）用 11 表示，其余地方对下一行没有影响用 00 表示，那么第 ii 行的状态就可以用一个 MM 为的二进制来表示。

注意 00 表示若干个横着的 1∗21*2 的长方形，连续奇数个 00 是无法分割的，可以在 DPDP 前预处理 [0,2m−1][0,2^m-1] 内所有满足“二进制下连续偶数个 00 ”的整数。

设 f[i][s]f[i][s] 表示第 ii 行的状态为 ss ，前 ii 行分割总数。

设 i−1i-1 行状态为 tt，tt 二进制下11 的地方 tt 必须为 00，其他地方 00 或 11 都可以。

f[i][s]=∑f[i−1][t]f[i][s]=\sum f[i-1][t] , 其中 t&s=0 t\&s=0 ,t∣st|s 满足“二进制下连续偶数个 00 ”

初值：f[0][0]f[0][0]=11 ，其余均为 00

目标：F[n][0]F[n][0] ,注意从第 00 行开始的 时间复杂度： O(2M∗2M∗N)=O(4M∗N)O(2^M*2^M*N)=O(4^M*N)

#include<bits/stdc++.h>
using namespace std;
long long f[12][1<<11];
int n,m;
bool v[1<<11];
bool check(int st)   //判断状态st中是否有奇数个0，如果有，返回false 
{
	int num=0;
	for(int i=0;i<m;i++)
		if(((st>>i) & 1)==0)num++;
		else
		{
			if(num&1)return false;
			num=0;
		}
	if(num&1)return false;
	return true;
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		memset(f,0,sizeof(f));
		memset(v,0,sizeof(v));
		
		for(int st=0;st<(1<<m);st++)
		{
			if(check(st))v[st]=1;
			//printf("st:%d v:%d\n",st,v[st]);
		}
		f[0][0]=1;
		for(int i=1;i<=n;i++)
			for(int s=0;s<1<<m;s++)
				for(int t=0;t<1<<m;t++)
					if((s&t)==0 &&v[s|t]==true)
						f[i][t]+=f[i-1][s];
						
		printf("%lld\n",f[n][0]);
	}

	return 0;
}

例3. P1879 [USACO06NOV]Corn Fields G

题意：给定一个 N∗M(N,M≤12)N*M(N,M\leq 12) 方格土地，有的地方不能种草，上、下、左、右相邻的格子不能都同时种草，询问有多少种种草方案？

分析： 第 ii 行能否种草，可以状态压缩为一个整数，存为 'p[i]'( 1 可以种，0 不能种)。这一行种植情况可以用 s 表示，如果 s|p[i]不等于 p[i] ,说明 s 状态中有 1 的位置在 p[i] 中是 0 (不能种草)，那 s 状态就是非法。

如何判断相邻格子是否同时种草，这存在左右相邻、上下相邻，左右相邻可以将 s 左移 1位、右移 1位，如果's&(s>>1)' 和 's&(s<<1)' 不等于 0 ，说明相邻位置上都是 1;

若第 ii 行的状态设为 ss，前 i 行总的合法的方案数用 f[i][s]f[i][s] 表示 i−1i-1 行的状态为 tt,状态 s 和 t 都合法（对应的 1 可以种草），且相同位置上都不会出现同时为 1 的情况（(s&t)==0）,可以得到转移方程：

f[i][s]+=f[i−1][t]f[i][s]+=f[i-1][t] 起点：f[0][0]=1f[0][0]=1

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e8;
int n,m,p[13];
long long f[13][1<<12];
bool check(int i,int s)
{
	if((s>>1)&s||(s<<1)&s)return false;
	if((p[i]|s)!=p[i])return false;
	
	return true;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		for(int j=0;j<n;j++)
		{
			int t;
			cin>>t;
			p[i]=p[i]|(t<<j);
		}
		
	f[0][0]=1;
	
	for(int i=1;i<=m;i++)
		for(int s=0;s<1<<n;s++)
		{
			if(check(i,s)) 
				for(int t=0;t< 1<<n;t++)
					if(check(i-1,t) && ((t&s)==0))
						f[i][s]=(f[i][s]+f[i-1][t])%mod;

		}		
	long long ans=0;
	for(int s=0;s<1<<n;s++)
		if(check(m,s))
			ans=(ans+f[m][s])%mod;
            
	cout<<ans;
	return 0;
}

例4. P1896 [SCOI2005]互不侵犯

题意：

在N×NN×N的棋盘里面放KK个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上、下、左、右，以及左上、左下、右上、右下八个方向上附近的各一个格子，共88个格子。(1≤N≤9,0≤K≤N2)(1 \leq N \leq 9,0 \leq K \leq N^2)

分析：

NN 比较小，一行中是否放国王的状态可以压缩为一个数表示。同行内国王不能相邻，可以通过左移、右移判断是否合法，相邻行之间两个状态可以用个左移 11 位左移 22 位和右移 11 位 22 位判断是否相互攻击。

本题要求摆放 KK 个国王,那么比 “P1879 [[USACO06NOV]Corn Fields G] ”那道题要增加一维信息，用于存储摆放的国王数。

定义状态 f[i][j][t]f[i][j][t] ,前 ii 行摆放了 jj 个国王 第 ii 行状态为 tt 的方案数,转移方程为：

f[i][j][t]+=f[i−1][j−cal(t)][s]f[i][j][t]+=f[i-1][j-cal(t)][s]

ss 是第 i−1i-1 行的状态，tt 是第 ii 行的状态，ss 和 tt 都合法且不存在互相攻击的情况。cal(t)cal(t) 计算状态 t 中 1 的个数(国王的数量)。

参考代码：点击

TIPS

对于网格填充问题，相邻之间不能同时为 1，为了优化，可以提前把合法的状态筛选出来，这样后面减少枚举状态数，从而优化。

例5. P2704 NOI2001炮兵阵地

题意：给定 N∗MN*M 的网格，网格状态是 PP (平原)和 HH（山地）,平原上的格子可以布置炮兵，但是炮兵会攻击左右和上下 2 个格子，在不相互攻击的情况下最多可以摆放多少个炮兵？

分析：

思路1：使用两个状态描述两相邻行的状态

由于会存在两行的相互攻击情况，可以定义状态 f[i][s][t]f[i][s][t] 表示第 ii 行的状态为 ss，第 i−1i-1 行的状态为 tt。

考虑上一个阶段状态应该是 f[i−1][t][k]f[i-1][t][k] ,即 ii 行状态为 ss，i−1i-1 状态为 tt，i−2i-2 行状态为 kk,在他们合法的情况下转移方程为

$dp[i][s][t]=max(dp[i][s][t],dp[(i-1)][t][k]+sum[s])$

空间复杂度为 O(N∗2M∗2M)O(N*2^M*2^M) ,可以使用 01 滚动数组，进行空间优化；

可以提前预处理，筛选出合法的状态来（相邻 1 个位置 2 个位置不能同时为 1，合法的状态数大大降低），时间复杂度进一步降低到 O(N∗∣S∣3)O(N*|S|^3)。

参考代码: 点击

思路2： 使用 3 进制压缩，用 3 进制描述一行的状态（实际上也是 2 行的状态） 2表示放置炮兵，1表示头顶对应格子有炮兵，0表示头顶是1 f[i][s] 表示前 i 行第 i 行的状态是 s最多放置的炮兵数量。

例6. P2831 NOIP2016愤怒的小鸟

题意：平面上有 nn 只给定坐标的小猪，原点位置有弹弓，弹弓发射小鸟，小鸟以抛物线 y=ax2+bxy=ax^2+bx 的轨迹飞行，碰到小猪就会把小猪消灭，消灭后飞行轨迹不变。 询问最少需要发射多少只小鸟才能消灭掉所有的小猪？

分析： 多只小猪可能共线，共线的小猪一次发射就可以全部消灭。对于抛物线 y=ax2+bxy=ax^2+bx，两个点就可以确定系数 aa 和 bb,那如何知道其他点是否通过该直线？

可以其他点是否共线用一个整数状压表示，用 line[i][j] 表示通过通过点 ii 和 jj，nn 个点的共线状态。

for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
  {
	if(i==j||fabs(x[i]-x[j])<eps)	continue;
	double a,b;
	equation(a,b,x[i],y[i],x[j],y[j]);//计算系数
	if(a>0)continue;
	for(int k=0;k<n;k++)
	if(check(a,b,k))line[i][j]|=(1<<k); //检查k是否在抛物线上
  }

接着考虑消灭全部小猪，最少发射次数，nn 个小猪是否被消灭，可以用状态 ss 表示,那么就可以用 f[s]f[s] 表示状态 ss 最少需要发射几次，针对 ss 中 00 (未消灭的小猪)，可能是单独被消灭，也可能一次消灭两个，消灭两个的同时，如果其他小猪共线，也会连带被消灭，那么 line[i][j] 可以排上用场。

核心代码：

dp[0]=0;
for(int s=0;s<(1<<n);s++)
	for(int i=0;i<n;i++)
	if((s&(1<<i))==0)
	  {
		 dp[s|(1<<i)]=min(dp[s|(1<<i)],dp[s]+1);
		 for(int j=i;j<n;j++)
		   dp[s|line[i][j]]=min(dp[s|line[i][j]],dp[s]+1);
		   break;
		}
	cout<<dp[(1<<n)-1]<<endl;

完整参考代码：点击

例7. P4011孤岛营救问题

题意：给定一个 N∗MN*M 的网格，相邻网格之间可能是墙，也可能是门，门上有锁子，需要对应的钥匙才能打开，一些格子中有钥匙，需要拿到对应的钥匙才能打开对应类型的门。询问从 (1,1)(1,1) 出发，到 (N,M)(N,M) 最少需要几步，如果无法到达输出 −1-1.

分析：

由于钥匙种类数比较少，可以把路线上获得的钥匙进行状压；为了能够描述清到那个位置，同时钥匙情况，可以用三维状态 (i,j,s)(i,j,s) 表示走到 (i,j)(i,j) 获取的钥匙情况为 ss；那么在三维空间中，就是无权图最短路问题了，可以直接 BFSBFS 求解。

参考代码：点击

例8. P3092 [USACO13NOV] No Change G

【题意简化】给定 k(k≤16)k(k\le 16) 枚硬币，每个硬币都有一定面值。给定 n(≤105)n(\le 10^5) 件商品，每个硬币可以购买连续一段商品，不设找零的情况下，如果能够购买 nn 物品，询问做多能留下多少钱？不能购买，输出 -1

【分析】硬币对应的 kk 较小，可以状压。

可以提前利用双指针预处理每枚硬币开始购买位置，算出购买区间的右端点，记为 f[i][l]f[i][l] , 表示硬币 ii 从 ll 开始购买，能够购买的右端点位置，利用双指针 O(kn)O(kn) 得到。

再定义 dp[s]dp[s] 使用硬币状态 ss 最多能够购买多少枚硬币，转移方程：

dp[s∣(1<<i)]=max(dp[s∣(1<<i)],f[i][dp[s]+1])dp[s|(1<<i)]=max(dp[s|(1<<i)],f[i][dp[s]+1]).

总时间复杂度：O(kn+2kk)O(kn+2^kk) ，参考代码：点击

例9. P3622APIO2007动物园

例10. P3959NOIP2017宝藏

例11 P2150NOI2015寿司晚宴

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 69ms
  4. Powered by Hydro v4.19.1 Modified by byx QQ465039728
  5. 陕ICP备2023000766号