题解 P2915 【[USACO08NOV]奶牛混合起来Mixed Up Cows】
N (4 <= N <= 16),定义状态值state（范围：0-216-1），表示当前含哪几头牛，如表：
牛 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
位序 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
取值 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1
含义 第i位取值为1/0,表示含/不含第(i+1)头牛
举例 49=0000 0000 0001 1001，表示含第1、4、5头牛
N头牛的身上的编号 s[1],s[2],…,s[N]
dp[last][state]表示最后一头牛为last，当前含牛的状态为state，共有多少组符合条件的队伍。
dp[2][2],2=00…0010(二进制仅表示第2头牛的第1位为1) 该状态表示仅含第2头牛，
所以：dp[2][2]表示最后一头牛是2，仅含第2头牛，混乱队伍数量
dp[2][5],5=00…001001(二进制仅表示含第1、4头牛)，这种情况不存在，dp[2][5]=0
初始情况，仅含1头牛，那么这头牛就是结尾
假设共含8头牛，下标列出各种初始情况
哪头牛
（last） 状态值
(二进制) 状态值
(十进制) 表示方法 参数含义 dp(last,state)
1 0000 0001 1 20 1<<0 若仅含第last头牛，则其状态state为1左移last-1位，或2的last-1次方 1
表示在仅有1头牛的情况下，属混乱状态。
2 0000 0010 2 21 1<<0
3 0000 0100 4 22 1<<0
4 0000 1000 8 23 1<<0
5 0001 1000 16 24 1<<0
6 0010 0000 32 25 1<<0
7 0100 0000 64 26 1<<0
8 1000 0000 128 27 1<<0 故，初始化程序：
for(last = 1; last <= n; last++)
{
state=1<<(last-1);// 仅含第last头牛，则其状态state为1左移last-1位
f[last][state] = 1;//有效状态进行初始化
}然后按状态、依次加入每头牛，进行迭代 for(state=1;state<=2n-1;state++) //或等价写法 for(state=1;state<=1<<n-1;state++)
//对每一种状态进行处理
//状态初值二进制00…01，十进制1:前n-1位为0，最后1位为1，仅含第1头牛
//状态最大值11…11，十进制2n-1，1<<n-1: n位均为1，表示含全部第1-n头牛
{
for(last=1;last<=n;last++) //依次对每种状态下、队伍尾牛为last的情况进行处理
{ //首先要判断第last头牛是否已经在state状态中
//如果不在，则dp[last][state]为不可能,无需处理
//这里要用到&二进制按位与运算
if(state & 1<<(last-1)==0)continue;// state & 1<<(last-1)=0表示last不在state状态
//若牛last在state中，为合法情况，需进一步进行处理
//即依次加入1头不在state中的牛，进行处理
for(newcow=1;newcow<=n;newcow++)
//从第1头到第n头依次处理
{ if(state & 1<<(newcow-1)==1)continue;// state & 1<<(newcow-1)=1表示
// newcow在state状态
//不能重复加入该点，不处理
//再判断加入newcow到队伍尾部后，队伍是否混乱
if(abs(s[last]-s[newcow])<k) )continue; //不混乱，也不需要处理
//若依然混乱，则需进行数据更新
//此时需更新的是以newcow为队尾，加上newcow以后状态的dp值
newstate=state | (1<<(newcow-1));//或newstate=state + (1<<(newcow-1))
dp[newcow][nowstate]+=dp[last][state];
}
}
}
state=2n-1;//等价于：state<=1<<n-1 ，最后的有效状态是包含所有牛
ans=0;//统计符合要求的方案数，初值为0
for(last = 1; last <= n; last++)
ans+=dp[last][state];//包含所有牛的状态下，队尾为1、2、3…、n
//累加即为所求结果
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[17],n,k1;
long long dp[16][1<<16],ans=0;
int main()
{
scanf("%d%d",&n,&k1);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
dp[i][1<<i]=1;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<n;j++)
if(i&(1<<j))
for (int k=0;k<n;k++)
if(!(i&(1<<k))&&abs(a[j]-a[k])>k1)
dp[k][i|(1<<k)]=dp[k][i|(1<<k)]+dp[j][i];
for(int i=0;i<n;i++)
ans=ans+dp[i][(1<<n)-1];
printf("%lld",ans);
return 0;
}