题解 P2915 【[USACO08NOV]奶牛混合起来Mixed Up Cows】
wjyyy
2018-07-02 17:34:23
[欢迎在博客食用](http://www.wjyyy.top/691.html)
## 解法：
首先我们看到数据范围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
```cpp
#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维枚举
```cpp
#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;
}
```