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

很久没做过状压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

## 输入输出格式

* 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.

4 1
3
4
2
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;
}

Subscribe

/* */