状压dp

emmm我太弱了,要不才不会来总结这个。

就是把状态压成二进制位,当做一个数,记在dp数组里,然后我们就有了所有状态,一般转移都是直接枚举每一个状态,所以状压的话复杂度超高,只有n很小的时候才能用,枚举每一个状态的话,就是(1<<i)呗,看看如何转移。

有的时候我们还可以预处理选一些状态的价值,转移的时候就很方便了。

预处理一个bin[i]数组表示,选第i个物品。

这样在枚举状态的时候,我们只要&一下bin数组,就知道这个状态选没选第i个物品,才能统计选这些物品的价值。

然后dp转移的时候,就枚举每个状态和每个状态里面的物品选不选。然后就可以了。

上一道题?

我是不会告诉你,我是通过这个题深入理解了状压dp。

luogu P3112

状压水题: 直接看即可:

#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~;

二进制拆分:

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(" ");
}

发表于 2018-08-29 12:01:48 in 知识点