题解 P3052 【[USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper】

shadowice1984 · 2017-10-20 13:20:40 · 题解

状态压缩动态规划

这道题是不能使用普通的线性dp的

因为每一头牛只能够用一次，这样会出现后效性

但是枚举全排列的n!做法又是承受不住n=18的数据范围

因此我们使用一个二进数j表示那些奶牛被选过。

令d[i][j]表示已经开了i架电梯，j是二进制数，第k位为1表示这个位置的奶牛被选过。

d[i][j]的值表示当前电梯里的重量。

那么如果存在d[i][j]这种方案，我们枚举k不属于j

那么就可以转移到d[i][j&(1<<k)]或者d[i+1][j&（1<<k)]

然后从前往后扫，扫到第一个存在j=2^n-1的方案即可

#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
int d[20][300000];
int n;int w[20];
int m;int up;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    up=pow(2,n);//定义上界
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=up-1;j++)
        {
            d[i][j]=0x3f3f3f3f;//初始化为∞
        }
    }
    for(int i=0;i<n;i++)
    {
        d[1][1<<i]=w[i];//边界条件，第一架电梯放那一头牛
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=up-1;j++)//存在性dp
        {
            if(d[i][j]!=0x3f3f3f3f)//如果存在
            {
                //printf("d[%d][%d]=%d\n",i,j,d[i][j]);
                for(int k=0;k<n;k++)//枚举k
                {
                    if((j&(1<<k))!=0)continue;//如果属于jcontinue掉
                    if(d[i][j]+w[k]<=m)
                    {
                        d[i][j|(1<<k)]=min(d[i][j|(1<<k)],d[i][j]+w[k]);
                        //printf("d[%d][%d]->d[%d][%d]=%d\n",i,j,i,j|(1<<k),d[i][j|(1<<k)]);
                    }
                    else
                    {
                        d[i+1][j|(1<<k)]=min(d[i][j|(1<<k)],w[k]);
                        //printf("d[%d][%d]->d[%d][%d]=%d\n",i,j,i+1,j|(1<<k),d[i][j|(1<<k)]);
                    }
                }
            }
        }
    }
    for(int i=0;i<=n;i++)
    {
        if(d[i][up-1]!=0x3f3f3f3f)//从后往前走
        {
            printf("%d",i);break;
        }
    }
    return 0;
}