状压dp

  • Z时代
  • 2024-01-10
  • 分类：综合

coding

状压dp

概述

状压dp就是用二进制表示状态，并且对其子集进行归并的动态规划。它基于基本的位运算，常出现在NOIP和省选中。

状压有明显的数据范围暗示，一般在20左右

三进制枚举

有时我们需要先枚举一个子集，再枚举这个子集的一个子集，此时我们经常二进制枚举两层再判断是否包含。这样很直接，但不如三进制枚举快速。

假设我们有集合$S$，我们需要$A\subseteq S$，$B\subseteq A$，此时$S$集合的元素有三种情况：只在$S$中；既在$S$中又在$A$中；同时在三个集合中。只有三种情况，于是我们可以三进制枚举。

三进制枚举模式代码：

for (int x = 0; x < (1 << n); ++x) {
    for (int y = x;; y = (y - 1) & x) {
        for (int i = 0; i < n; ++i) {
            if ((x >> i) & 1) {
                // Do something
            }
            if ((y >> i) & 1) {
                // Do something
            }
        }
        // Do something
        if (y == 0) break;
    }
}

代码中关键的语句是y = (y - 1) & x,-1保证状态不同且最接近原状态&保证是子集。

例题：P1896 [SCOI2005]互不侵犯

题意很简单，就是在$N\times N$的棋盘中放$K$个国王，使得国王之间不互吃。

我们很容易想到状压dp，我们按行枚举，再枚举上一行的状态，再枚举这一行的状态，再枚举价格，转移即可。

对于两层枚举状态，我们可以使用两层二进制枚举，也可以使用上面的三进制枚举。其中三进制枚举复杂度更低，也不需要检验正确性，其中$S$集合为所有状态，$A$集合为这一行不会被上一行影响的部分，$B$集合为当前行的状态。

这应该是此题除了打表最快的做法了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9+7,MAXN=10,MAXP=1<<9,MAXK=85;
int N,K,maxp,ilg[MAXP]/*illegal*/,cnt[MAXP];
LL f[MAXN][MAXP][MAXK],ans;
int main(){
	scanf("%d%d",&N,&K);
	maxp=1<<N;
	for(int i=0;i<maxp;i++){
		for(int j=0;j<N;j++){
			if((i>>j)&1){
				cnt[i]++;
				if(((i>>j)&3)==3)
					ilg[i]=1;
			}
		}
		f[1][i][cnt[i]]=!ilg[i];
	}
	for(int i=2;i<=N;i++)/*line*/
		for(int j=0;j<maxp;j++){/*last*/
			if(ilg[j])
				continue;
			int no=((maxp-1)^(j|(j<<1)|(j>>1)))%maxp;
			for(int k=no;;k=(k-1)&no){/*current*/
				if(ilg[k])
					continue;
				if(k>=maxp)
					return 0;
				for(int l=0;l+cnt[k]<=K;l++)
					f[i][k][l+cnt[k]]+=f[i-1][j][l];
				if(!k)
					break;
			}
		}
	for(int i=0;i<maxp;i++)
		ans+=f[N][i][K];
	printf("%lld",ans);
	return 0;
}

枚举排列

对于一个排列，我们有时可以对于它的子集进行操作，此时可以使用状压dp。

但有时我们面对的不是一个排列，而是有重复元素的数列，此时我们需要按照以下公式去重（用多重集合的排列） $$\frac{n!}{\prod n_i!}$$ 其中$n_i$为每种元素的个数

例题：P4163 [SCOI2007]排列

以上是 状压dp 的全部内容， 来源链接： utcz.com/z/509085.html

回到顶部