洛谷 P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows 题解【状态压缩】【DP】

作者: wjyyy 分类: DP,二进制,状态压缩,解题报告 发布时间: 2018-07-02 17:28

点击量:29

 

   很久没做过状压DP了,这道状压DP有很多技巧

 

题目描述

Each of Farmer John’s N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

 

Gangsta cows are rebellious and line up to be milked in an order called ‘Mixed Up’. A cow order is ‘Mixed Up’ if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a ‘Mixed Up’ lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

 

How many different ways can N cows be Mixed Up?

 

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

 

POINTS: 200

 

约翰家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气,为表达不满的情绪,她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队伍中,相邻奶牛的编号之差均超过K。比如当K = 1时,1, 3, 5, 2, 6, 4就是一支混乱的队伍, 而1, 3, 6, 5, 2, 4不是,因为6和5只差1。请数一数,有多少种队形是混乱的呢?

 

输入输出格式

输入格式:

* Line 1: Two space-separated integers: N and K

 

* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i

 

输出格式:

* Line 1: A single integer that is the number of ways that N cows can be ‘Mixed Up’. The answer is guaranteed to fit in a 64 bit integer.

 

输入输出样例

输入样例#1:
4 1
3
4
2
1
输出样例#1:
2

说明

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

 

解法:

   首先我们看到数据范围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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */