---

title : 狀壓DP
date : 2022-3-5
tags : ACM,圖論,動態規劃
author : Linno

---

狀壓DP

狀態壓縮，是利用二進制數的性質對問題進行優化的一種算法，經常與搜索和DP結合。

狀態壓縮動態規劃，俗稱狀壓DP。在動態轉移的過程中用二進制數表示狀態，并利用位運算的性質可使得枚舉方案大大減少。

前置知識

位運算基礎

判斷數字x二進制下第i位是不是1。

if(((1<<(i-1))&x)>0)

將數字x二進制下第i位改成1

x=x|(1<<(i-1)) //改成0的情況改成x=x&~(1<<(i-1))

將數字x最右邊的1去掉

x=x&(x-1) //也是我們熟知的lowbit

數字x的二進制下1的個數

int count(int x){int res=0;while(x){res++;x&=(x-1);}return res;}

圖論應用

狀壓DP+圖論狀態轉移舉例

for(int S=0;S<(1<<n);S++) //可以理解為n個點的選或不選for(int i=0;i<n;i++) if(S&(1<<i))for(int j=0;j<n;j++) //轉移點if(!(S&(1<<j))&&G[i][j]) //j不在點集中且i到j有路徑dp[j][S|(1<<i)]=min(dp[j][S|(1<<i)],dp[i][S]+G[i][j]);//S表示點集，j是轉移結點，G[i][j]是轉移代價

生成子集

for(int subs=s&(s-1);subs;subs=s&(subs-1)) //子集，可生成子圖 //subs=(subs-1)&s 可以枚舉s的子集

有興趣的同學可以搜一下斯坦納樹。

例題

P1896 [SCOI2005]互不侵犯

模板題：n*n的格子里面放k個國王，國王附近八個格子內沒有國王，可以有多少種方案？

#include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=10; const int mod=1e9+7;int count(int x){int res=0;while(x){res++;x&=(x-1);}return res;} int lb(int x){return x&(-x);}int n,K,ans=0,dp[N][(1<<10)][N*N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>K;for(int j=0;j<(1<<n);j++){if(j&(j<<1)) continue;dp[1][j][count(j)]=1; } for(int i=2;i<=n;i++){for(int j=0;j<(1<<n);j++){ //枚舉子集 if(j&(j<<1)) continue; //左右互不侵犯 for(int k=0;k<(1<<n);k++){ //前一行的狀態if(k&(k<<1)) continue;if(!((j&k)||(j&(k<<1))||((j<<1)&k))){ //當前狀態滿足和上一行的狀態互不侵犯 int num=count(j);//,num2=count(k);for(int p=0;p<=K;p++){dp[i][j][p+num]+=dp[i-1][k][p];}}}}}for(int j=0;j<(1<<n);j++){if(j&(j<<1)) continue;ans+=dp[n][j][K];}cout<<ans<<"\n";return 0; }

luoguP3694 邦邦的大合唱站隊

給定n個人m種顏色排成一列，可以抽出k個人將他們以任意順序插回，問最少k的最小值使得每種顏色的人站在一起。

狀態轉移方程$f[S]=min(f[Sxor(1<<j)]+num[j]?s[r][j]+s[l][j])$

其中$l,r$表示最后一個樂隊所對應的區間。

#include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e5+7;int n,m,a[N],num[25],sm[1<<21]; int sum[N][22],dp[1<<21];void dfs(int x,int s,int b){ //dp初始狀態——每種狀態中的顏色順序排好的花費 if(x==m) return;if(b) sm[s|(1<<x)]=sm[s]+num[x+1],dfs(x+1,s|(1<<x),1),dfs(x+1,s|(1<<x),0);else dfs(x+1,s,1),dfs(x+1,s,0); }signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j];sum[i][a[i]]++; //每種顏色的前綴和 num[a[i]]++;}dfs(0,0,0);dfs(0,0,1);memset(dp,inf,sizeof(dp));dp[0]=0;for(int i=1;i<(1<<m);i++){ //枚舉狀態 for(int j=1;j<=m;j++){ //枚舉顏色 if(i&(1<<(j-1))){ int l=sm[i^(1<<j-1)],r=sm[i];dp[i]=min(dp[i],dp[i^(1<<(j-1))]+(r-l)-(sum[r][j]-sum[l][j]));}} }cout<<dp[(1<<m)-1]<<"\n";return 0; }

[NOI2001] 炮兵陣地

題意：給定N×M的格子，有些地方不能放炮，炮之間不能相互攻擊到，問最多能放多少個炮。（炮的攻擊范圍是上下左右兩格以及自己所在格子）。

dp[i][j][k]表示兩行狀態分別為i和j時的答案，然后第三維用來滾動就ok了。

#include<bits/stdc++.h> using namespace std; const int N=1<<10;int n,m,mp[105],f[N][N][2],sum[N],ans=0; //f[i][j]表示前一行是狀態i,后一行是狀態j的答案，第三位用來滾動 bool g[N]; char ch;int getsum(int x){ //統計1的個數 int res=0;while(x){res+=(x&1);x>>=1;} return res; }signed main(){cin>>n>>m;int M=(1<<m);for(int i=0;i<n;i++){for(int j=0;j<m;j++){ch=getchar();while(ch!='P'&&ch!='H') ch=getchar();if(ch=='H') mp[i]=mp[i]<<1|1;else mp[i]=mp[i]<<1;} } for(int i=0;i<M;i++) sum[i]=getsum(i); //預處理 for(int i=0;i<M;i++){for(int j=0;j<M;j++){ //枚舉前兩行的狀態和答案 if((i&j)||(i&mp[0])||(j&mp[1])||(i&(i<<1))||(j&(j<<1))||(i&(i<<2))||(j&(j<<2))) continue;f[i][j][1]=sum[i]+sum[j];}}for(int i=2;i<n;i++){ //枚舉行 for(int j=0;j<M;j++){ //枚舉第i-1行狀態 if((j&mp[i-1])||(j&(j<<1))||(j&(j<<2))) continue;for(int k=0;k<M;k++){ //枚舉第i行狀態 if((k&(k<<1))||(k&(k<<2))||(k&mp[i])||(k&j)) continue;for(int v=0;v<M;v++){ //枚舉第i-2行狀態 if(v&(v<<1)||(v&(v<<2))||(v&j)||(v&k)||(v&mp[i-2])) continue;f[j][k][i%2]=max(f[j][k][i%2],f[v][j][(i-1)%2]+sum[k]);}}}}for(int i=0;i<M;i++){for(int j=0;j<M;j++){ans=max(ans,f[i][j][(n-1)%2]); //取最大值 }}cout<<ans<<"\n";return 0; }

參考文獻

https://www.bilibili.com/video/BV1Z4411x7Kw

https://www.cnblogs.com/ljy-endl/p/11627018.html

總結

以上是生活随笔為你收集整理的【算法竞赛学习笔记】状压DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。