状态压缩DP学习心得
Nemlit
2018-08-19 15:40:32
#### 状态压缩就是将一行的状态压成一个二进制数，这个数的二进制形式反映了这一行的情况
#### 比如0100111的意义为：这一排的第一个数没被使用，第二个被占用了，第三四个没被占用，第五六七个被占用
#### 我们知道位运算和状压DP一样，也是在二进制下进行的，所以位运算往往可以解决很多问题
## 我们来看看状压DP（位运算）的常用操作：
#### 有了这些位运算的帮助，我们便可以更加容易的对每一排的状态进行处理
#### 我们来看到状态压缩DP的经典问题（博主正在缓慢更新ing）
## 一、P1879 [USACO06NOV]玉米田Corn Fields
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define maxn 20
#define mod 100000000
il int read()
{
re int x=0,k=1;re char c=getchar();
while(c<'0'||c>'9'){if(c=='-') k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int m,n,a[maxn][maxn],s[maxn],dp[maxn][1<<maxn];
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;++i)
{
for(re int j=1;j<=m;++j)
{
a[i][j]=read();
s[i]<<=1;
s[i]+=a[i][j];
}
}
dp[0][0]=1;
for(re int i=1;i<=n;++i)
{
for(re int j=0;j<(1<<m);++j)//这一行状态
{
if((s[i]&j)==j&&!(j&(j<<1))&&!(j&(j>>1)))
{
for(re int k=0;k<(1<<m);++k)//上一行状态
{
if(!(j&k))
{
(dp[i][j]+=dp[i-1][k])%=mod;
}
}
}
}
}
re int ans=0;
for(re int i=0;i<(1<<m);++i)
{
(ans+=dp[n][i])%=mod;
}
printf("%lld",ans);
return 0;
}
```
## 二、P2622 关灯问题II
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define inf 123456789000000
#define int long long
#define maxn 11
#define maxm 105
il int read()
{
re int x=0,k=1;re char c=getchar();
while(c<'0'||c>'9'){if(c=='-') k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int n,m,dp[1<<maxn],a[maxm][maxn];
il int doit(int x,int t)
{
re int temp=0;
for(re int i=1;i<=n;++i)
{
if(a[t][i]==0) temp=(temp<<1)+(x%2);
else if(a[t][i]==1) temp<<=1;
else temp=(temp<<1)+1;
x>>=1;
}
return temp;
}
signed main()
{
n=read(),m=read();
for(re int i=1;i<=m;++i) for(re int j=1;j<=n;++j) a[i][j]=read();
for(re int i=0;i<(1<<n)-1;++i) dp[i]=inf;
for(re int i=(1<<n)-1;i>=0;--i)
{
if(dp[i]!=inf)
{
for(re int j=1;j<=m;++j)
{
re int temp=doit(i,j);
dp[temp]=min(dp[i]+1,dp[temp]);
}
}
}
dp[0]==inf?puts("-1"):printf("%lld",dp[0]);
return 0;
}
```
## 三、P3092 [USACO13NOV]没有找零No Change
```
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
inline int read(){
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int n,k,c[30],w[100005],dp[70000],ans=-1,sum[100005],tot,lo[30];
bool use[30],vis[100005];
inline void init()
{
k=read(),n=read();
for(int i=1;i<=k;i++)
{
c[i]=read();
tot+=c[i];
}
for(int i=1;i<=n;i++)
{
w[i]=read();
sum[i]=sum[i-1]+w[i];
}
lo[1]=1;
for(int i=2;i<=k;i++)
{
lo[i]=lo[i-1]<<1;
}
}
inline void work()
{
int ma=(1<<k);
for(int i=0;i<ma;i++)
{
for(int j=1;j<=k;j++)
{
if(i&lo[j])
{
int temp=upper_bound(sum+1,sum+n+1,sum[dp[i^lo[j]]]+c[j])-sum-1;
dp[i]=max(dp[i],temp);
}
}
}
for(int i=0;i<ma;i++)
{
if(dp[i]==n)
{
int cnt=0;
for(int j=1;j<=k;j++)
{
if(i&lo[j])
{
cnt+=c[j];
}
}
ans=max(ans,tot-cnt);
}
}
printf("%d",ans);
}
signed main()
{
init();
work();
return 0;
}
```
## 四、P2704 炮兵阵地
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
re int x=0,k=1;re char c=getchar();
while(c<'0'||c>'9'){if(c=='-') k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
il int read2()
{
re char c=getchar();
while(c!='H'&&c!='P')c=getchar();
return c=='H'?1:0;
}
#define maxn 11
#define maxm 101
int n,m,sum[1<<maxn],s[maxm],dp[1<<maxn][1<<maxn][maxm],st[1<<maxn];
il int BSGS(int s)
{
re int ans=0;
while(s)
{
if(s&1) ++ans;
s>>=1;
}
return ans;
}
signed main()
{
//freopen("a.in","r",stdin),freopen("a.out","w",stdout);
n=read(),m=read();
for(re int i=1;i<=n;++i)
{
for(re int j=1;j<=m;++j)
{
s[i]=(s[i]<<1)+read2();
}
}
for(re int i=0;i<(1<<m);++i)
{
sum[i]=BSGS(i);
st[i]=(!(i&(i<<1))&&!(i&(i<<2)));
}
for(re int i=0;i<(1<<m);++i)
{
for(re int j=0;j<(1<<m);++j)
{
if(!(i&j)&&st[j]&&!(j&s[2])&&!(i&s[1])&&st[i])
{
dp[i][j][2]=sum[i]+sum[j];
}
}
}
for(re int i=3;i<=n;++i)
{
for(re int j=0;j<(1<<m);++j)
{
if(!(s[i]&j)&&st[j])
{
for(re int k=0;k<(1<<m);++k)
{
if(!(s[i-1]&k)&&!(j&k)&&st[k])
{
for(re int l=0;l<(1<<m);++l)
{
if(!(l&s[i-2])&&!(k&l)&&!(j&l)&&st[l])
{
dp[k][j][i]=max(dp[k][j][i],dp[l][k][i-1]+sum[j]);
}
}
}
}
}
}
}
re int ans=0;
for(re int i=0;i<(1<<m);++i)
{
for(re int j=0;j<(1<<m);++j)
{
ans=max(ans,dp[i][j][n]);
}
}
printf("%d",ans);
return 0;
}
```
## 五、P1896 [SCOI2005]互不侵犯
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 105
#define maxr 20
using namespace std;
inline int read(){
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
ll n,k,ans,cnt,s[maxn],num[maxn],dp[maxr][maxn][maxn];
inline void init()
{
n=read(),k=read();
for(int i=0;i<(1<<n);i++)
{
if(i&(i<<1))
{
continue;
}
s[++cnt]=i;
int t=0;
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
t++;
}
}
num[cnt]=t;
}
}
inline void work()
{
dp[0][1][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int l=0;l<=k;l++)
{
if(l>=num[j])
{
for(int t=1;t<=cnt;t++)
{
if(!(s[t]&s[j])&&!(s[t]&(s[j]<<1))&&!((s[t]<<1)&s[j]))
{
dp[i][j][l]+=dp[i-1][t][l-num[j]];
}
}
}
}
}
}
for(int i=1;i<=cnt;i++)
{
ans+=dp[n][i][k];
}
cout<<ans;
}
int main()
{
init();
work();
return 0;
}
```
## 六、P3959 宝藏
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
#define debug printf("PassLine:%d\n", __LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout);
#define maxn 15
#define maxm 1005
#define inf 123456789
il int read()
{
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int n,m,a[maxn][maxn],dis[maxn],dp[1<<maxn],ans=inf;
il void dfs(int s)
{
for(re int i=1;i<=n;++i)
{
if(s&(1<<(i-1)))
{
for(re int j=1;j<=n;++j)
{
if(!(s&(1<<(j-1)))&&a[i][j]!=inf)
{
if(dp[1<<(j-1)|s]>dp[s]+dis[i]*a[i][j])
{
re int temp=dis[j];
dis[j]=dis[i]+1;
dp[1<<(j-1)|s]=dp[s]+dis[i]*a[i][j];
dfs(1<<(j-1)|s);
dis[j]=temp;
}
}
}
}
}
}
int main()
{
//file(a);
n=read(),m=read();
for(re int i=1;i<=n;++i) for(re int j=1;j<=n;++j) a[i][j]=inf;
for(re int i=1,u,v,w;i<=m;++i)
{
u=read(),v=read(),w=read();
a[u][v]=a[v][u]=min(w,a[u][v]);
}
for(re int i=1;i<=n;++i)
{
for(re int j=0;j<(1<<n);++j) dp[j]=inf;
for(re int j=1;j<=n;++j) dis[j]=inf;
dis[i]=1;
dp[1<<(i-1)]=0;
dfs(1<<(i-1));
ans=min(ans,dp[(1<<n)-1]);
}
printf("%d",ans);
return 0;
}
```