状压dp水题题解来一发

四道大水题的解题报告
前几天老刘找我们聊过之后,要我最近看看状压dp,于是乎就刷了几道,结果第一题用了深搜,第二题用了模拟,终于到绿题了才是正经dp,下面是四道水题的解题报告
yeah,DJ

洛谷P2915

题目大意

给一个长为n的序列,将序列排序,要求每相邻两个数的差值要超过给定值k,问有多少种序列符合要求

题解

用一个二进制整数j的第k位(从右往左)表示序列中是否含有第k个数
e.g.
j = 10101010 j=10101010 j=10101010时,序列中包含第 2 , 4 , 6 , 8 2,4,6,8 2,4,6,8个数

用dp[i,j]表示以第i个数结尾,且当前取数情况为j的合法序列数量
很显然, 10101010 10101010 10101010这种情况,一定可以由 10101000 10101000 10101000这一种情况转移得到,那么我们只要枚举每一种情况的每一位,如果这一位已经有数,那么就枚举没有数的每一位,看它是否满足情况

for(int i=0;i<n;i++) dp[i][1<<i]=1;
int maxn=1<<n;
for(int i=0;i<maxn;i++)//枚举每一种情况
    for(int j=0;j<n;j++)//枚举每一位
    {
        if(i&(1<<j))//已经包含了
        {
            for(int l=0;l<n;l++)//枚举每一位
            {
                if(!(i&(1<<l))&&abs(s[j]-s[l])>k)//该位还没被填上且满足要求
                dp[l][i|(1<<l)]+=dp[j][i];//转移
            }
        } 
    }

洛谷P3052

题目大意

给出n个物品,体积为w[i],现把其分成若干组,要求每组总体积<=W,问最小分组。(n<=18)

题解

看题目数据范围就很状压,用一个二进制数i的第k位表示是否已经将第k个物品分好了组,f[i]表示第i种情况属于哪一组,g[i]表示i这种情况下,i这一组剩下的体积。枚举每一个i,枚举i的每一位j,如果剩余体积还能把第j’个物品放下,就转移

    for(int i=0;i<(1<<n);i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<(j-1))) continue;//这一位已经取了
            if(g[i]>=c[j]&&f[i|(1<<(j-1))]>=f[i])//放得下
            {
                f[i|(1<<(j-1))]=f[i];
                g[i|(1<<(j-1))]=max(g[i|(1<<(j-1))],g[i]-c[j]);
            }
            else if(g[i]<c[j]&&f[i|(1<<(j-1))]>f[i])//放不下
            {
                f[i|(1<<(j-1))]=f[i]+1;
                g[i|(1<<(j-1))]=max(g[i|(1<<(j-1))],w-c[j]);
            }
        }
    }

洛谷P2622

题目大意

n盏灯,m个按钮,a[i,j]表示第i个按钮对j盏灯的控制效果,若a[i,j]为1,那么若灯开着,将其熄灭,若a[i,j]为-1,那么若灯关着,将其打开,若a[i,j]为0,则不管,刚开始灯全亮着及所有控制效果,求最少的按按钮的次数。 ( n < = 10 , m < = 100 ) (n<=10,m<=100) (n<=10,m<=100)

题解

这个状压似乎就很显然了,i的每一位表示这盏灯是否开着,枚举每一位转移就行
dp[(1<倒着往前推

    memset(dp,0x3f,sizeof(dp));
    int maxn=(1<<n)-1;
    dp[(1<<n)-1]=0;
    for(int i=maxn;i>=0;i--)
    {
        for(int j=1;j<=m;j++)
        {
            int now=i;
            for(int k=0;k<n;k++)
            {
                if((i&(1<<k))&&a[j][k+1]==1) now^=(1<<k);
                if((!(i&(1<<k)))&&a[j][k+1]==-1) now^=(1<<k);
            }
            dp[now]=min(dp[now],dp[i]+1);
        }
    }

洛谷P2622

题目大意

一块mn的土地,每个11的方块都有一个状态,若状态为1,则可以种草,为0则不行,不能有草地相邻(有邻边),问有几种方案 m , n < = 12 m,n<=12 m,n<=12

题解

这个明显是个二维状压dp(吧),枚举每一排的状态,这一排每一块是否种草,然后只要这一行是合法的,并且和上一行也没有草地相邻,就可以将上一行的对应状态的答案累加到这一行的这种状态中。
最后累加最后一行的每一种状态的答案

    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    dp[i]=(dp[i]<<1)+field[i][j];
    //field[i,j]表示这一块土地是否能种草
    //dp[i]表示最多最多的合法状态
    int maxn=1<<n;
    for(int i=0;i<maxn;i++)
        st[i]=(((i&(i<<1))==0) && ((i&(i>>1))==0));
    //这个是保证左右都没有草地相邻
    f[0][0]=1;
    for(int i=1;i<=m;i++)
    for(int j=0;j<maxn;j++)
    if(st[j]&&((j&dp[i])==j))
    //没有左右相邻的而且每一块要种草的都是能种的
    for(int k=0;k<maxn;k++)
    if((k&j)==0) f[i][j]=(f[i][j]+f[i-1][k])%mod;
    //上下两排不相邻
    int ans=0;
    for(int i=0;i<maxn;i++)
    ans=(ans+f[m][i])%mod;

peace

你可能感兴趣的