526互联

状态压缩DP

发布时间 2023-11-05 09:12:49作者: Gao_l

关于状态表示形式的优化方式。

使用场景：需要记录不超过二进制数位(通常22位以内)的bool信息的DP问题。

常见的位操作

简单操作

  1. 任何二进制数位 &1 得到它本身。
  2. 任何二进制数位 ^1 则取反。
  3. 任何二进制数位 &0 则赋值为0。
  4. 任何二进制数位 |1 则赋值为1。

混合操作

  1. (n>>k&1) 取出二进制下n的第k位(从右往左)。
  2. n&((1<<k)-1) 取出二进制下n的右k位。
  3. n^(1<<k) 将二进制下n的第k位取反。
  4. n|(1<<k) 将二进制下n的第k位赋值为1。
  5. n&(~(1<<k)) 将二进制下n的第k位赋值为0。

题目

海贼王的伟大航路

状态

dp[i][j]表示到达点 j时经过的点的状态为二进制下的i的最少时间。
答案：cout<<dp[(1<<n)-1][n-1];

状态转移

for(int i=0;i<(1<<n);i++)//经过的状态
	for(int j=0;j<=n-1;j++)//当前到达的点j
		if((i>>j)&1)
			for(int k=0;k<=n-1;k++)//枚举上一个点k
				if((i>>k)&1)
					dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+t[k][j]);

初始状态

dp[1][0]=0，其余为极大值。

P1879 [USACO06NOV] Corn Fields n

状态

dp[i][j]表示第i行种草状态为二进制下的j的方案数。
答案：
ans=(ans+dp[m][i])%mod;

状态转移

for(inti=1;i<=m;i++)//行
	for(intj=0;j<(1<n;j++)//i行种草的状态
		for(int k=0;k<(1<n;k+)//i-1行种草
			if(check(i,j)=true)//肥沃、上左右不冲突
				dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;

初始状态

dp[0][0]=1

check

check(i,j)保证第i行的草必须在肥沃的土地

  1. if((j&soil[i])==j)则种草合法；
  2. if((j&k)==0)则上下不冲突；
  3. if((j&(j<<1))==0)，则左右不冲突