题解 P2915 【[USACO08NOV]奶牛混合起来Mixed Up Cows】

2018-07-02 17:34:23


欢迎在博客食用

解法:

   首先我们看到数据范围N≤16,就可以想到状态压缩,接着看就会看到方案数的选择,那么就可以尝试DP。

   首先我想的是,用三维数组$f[i][j][k]$表示当前已经选了i头牛,上一个选的是j,当前状态压缩为k。我们主要关注的是第二维,因为方案合不合法就看与自己前面的那一个的编号差距。因此有了方案:枚举当前要放的牛m,再枚举之前放过的牛c,这样枚举1到65535,找出有c且没有m的状态。为了避免冲突,我们还要在最外面枚举当前选了多少头牛。

   因此这个时间复杂度是$O(N^3\times 2^n)$的,乘出来有2亿我为什么要乘出来

   所以这种做法是不可行的,不过bzoj时限比较宽,可以过,luogu开O2再加玄学剪枝就可以了,emmm。。。代码贴在最后。

正解:

   学过集合/了解二进制的同学应该知道,我们如果用二进制枚举子集,在合法条件下,后枚举的一定包含某些先枚举的,例如111011会在110011后枚举到。因为数值越来越大,1也会趋向越多。那么我们就可以使大体趋势跟随1~65535枚举来更新我们的DP状态。首先我们定义DP数组$f[i][j]$,表示当前最后一头牛是i时状态压缩为j的方案数。那么我们在二进制枚举下,枚举数对(j,k),找到合法数对,使得在当前二进制状态下,j被放进去过,且为最后一头,同时k没有被放进去过,找到后更新状态。因为1存的是已经放过的奶牛,所以在奶牛增加的情况下,通过刷表法更新之后状态下的奶牛,就不会出现紊乱/冲突了。

Code:100pts

#include<cstdio>
#include<cstring>
int abs(int x)
{
    return x>0?x:-x;
}
long long f[18][66666];//当前放到i号牛时压位为j
int num[18];

int main()
{
    memset(f,0,sizeof(f));
    int n,K;
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    for(int i=1;i<=n;i++)
        f[i][1<<(i-1)]=1;
    //正在枚举的状态一定包含已经枚举过的状态
    for(int i=1;i<(1<<n);i++)
        for(int j=1;j<=n;j++)//j是来自
            for(int k=1;k<=n;k++)//k是当前
                if(abs(num[j]-num[k])>K&&((1<<(j-1))&i)&&(((1<<(k-1))&i)==0))
                    f[k][((1<<(k-1))|i)]+=f[j][i];//刷表
    long long sum=0;
    for(int i=1;i<=n;i++)//统计答案
        sum+=f[i][(1<<n)-1];
    printf("%lld\n",sum);
    return 0;
}

Code:80~100pts(O2) 4维枚举

#include<cstdio>
#include<cstring>
int abs(int x)
{
    return x>0?x:-x;
}
long long f[2][18][66666];//当前放到i号牛时压位为j
int num[18];
int lowbit(int x)
{
    return x&(-x);
}
int cnt(int x)//二进制数里有多少个1
{
    int sum=0;
    while(x)
    {
        sum++;
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    memset(f,0,sizeof(f));
    int n,k,tmp;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    for(int i=1;i<=n;i++)
        f[1][i][1<<(i-1)]=1;
    for(int i=2;i<=n;i++)//放第i头牛
        //可行状态
        for(int j=1;j<=n;j++)
            for(int t=1;t<=n;t++)
            {
                if(abs(num[j]-num[t])>k)
                {
                    if(t==1)//这是什么玄学剪枝
                        tmp=2;
                    else
                        tmp=1;
                    for(int k=1;k<1<<n;k+=tmp)
                        if(cnt(k)==i-1)
                        {
                            if(!((1<<(j-1))&k)&&((1<<(t-1))&k))//j没有被用过且t被用过
                                f[i&1][j][k|(1<<(j-1))]+=f[i&1^1][t][k];
                        }
                }
            }
    long long sum=0;
    for(int i=1;i<=n;i++)//统计方案
        sum+=f[n&1][i][(1<<n)-1];
    printf("%lld\n",sum);
    return 0;
}