状压dp
wangyitong
2018-08-29 12:01:48
~~emmm我太弱了，要不才不会来总结这个。~~
就是把状态压成二进制位，当做一个数，记在dp数组里，然后我们就有了所有状态，一般转移都是直接枚举每一个状态，所以状压的话复杂度超高，只有n很小的时候才能用，枚举每一个状态的话，就是(1<<i)呗，看看如何转移。
有的时候我们还可以预处理选一些状态的价值，转移的时候就很方便了。
预处理一个bin[i]数组表示，选第i个物品。
这样在枚举状态的时候，我们只要&一下bin数组，就知道这个状态选没选第i个物品，才能统计选这些物品的价值。
然后dp转移的时候，就枚举每个状态和每个状态里面的物品选不选。然后就可以了。
上一道题？
~~我是不会告诉你，我是通过这个题深入理解了状压dp。~~
[luogu P3112](https://www.luogu.org/problemnew/show/P3112)
状压水题:
直接看即可：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define ri register int
#define int long long
using namespace std;
template<class R> void in(R &x)
{
x=0;
bool f=0;
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();
}
if(f)
x=-x;
}
struct node
{
int h,w,lim;
} cow[25];
int bin[50],tot,n,height,tmp[1<<21],dp[1<<21],a[50];
int ans=-1;
inline void Binary_split(int t)//二进制拆分，我在下面把它封装好了，可尽情使用。调试时超好用
{
memset(a,0,sizeof a);
int len=0,flag=0;
for(ri i=20; i>=1; --i)
{
if(t>=bin[i]&&flag==0)
{
flag=1;
len=i;
a[i]=1;
t-=bin[i];
}
else if(t>=bin[i]&&flag)
{
a[i]=1;
t-=bin[i];
}
}
for(ri i=1; i<=len; ++i)
printf("%lld",a[i]);
puts(" ");
}
signed main()
{
bin[1]=1;
for(ri i=2; i<=20; ++i)
bin[i]=bin[i-1]<<1;//bin[i]表示选第i个；
in(n),in(height);
for(ri i=1; i<=n; ++i)
{
in(cow[i].h),in(cow[i].w),in(cow[i].lim);
tot+=cow[i].h;
}
/*for(ri i=1; i<=n; ++i)
{
printf("%lld %lld %lld\n",cow[i].h,cow[i].w,cow[i].lim);
}*/
if(tot<height)
return puts("Mark is too tall"),0;
for(ri i=1; i<(1<<n); ++i)//预处理每个状态的贡献
for(ri j=1; j<=n; ++j)
if(i & bin[j])//如果i&bin[j]==1,那么说明i这个状态里选了第j这个牛
{
/*puts("枚举状态");
Binary_split(i);
puts("枚举二进制下哪一位1的情况");
Binary_split(bin[j]);
puts("把他们&一下");
Binary_split(i & bin[j]);
puts("减一下试试？？？");
Binary_split((i-bin[j]));*/
tmp[i]+=cow[j].h;
}
memset(dp,0xcf,sizeof dp);
dp[0]=2333333333333;
for(ri i=1; i<(1<<n); ++i)
{
for(ri j=1; j<=n; ++j)//枚举每个状态i选不选第j个牛,
if(i & bin[j])
dp[i]=max(dp[i],min(dp[i-bin[j]]-cow[j].w,cow[j].lim));
if(tmp[i]>=height)
ans=max(ans,dp[i]);
}
if(ans==-1)
puts("Mark is too tall");
else
printf("%lld",ans);
return 0;
}
```
Bingo~;
二进制拆分：
```cpp
inline void Binary_split(int t)
{
memset(a,0,sizeof a);
int len=0,flag=0;
for(ri i=20; i>=1; --i)
{
if(t>=bin[i]&&flag==0)
{
flag=1;
len=i;
a[i]=1;
t-=bin[i];
}
else if(t>=bin[i]&&flag)
{
a[i]=1;
t-=bin[i];
}
}
for(ri i=1; i<=len; ++i)
printf("%lld",a[i]);
puts(" ");
}
```