# 动态规划 | [USACO08NOV]奶牛混合起来Mixed Up Cows

## Description

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.

## Input

• 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

## Output

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

## Sample Input

4 1
3
4
2
1


## Sample Output

2


## Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxs 65537
#define maxn 17
using namespace std;
typedef long long ll;
ll f[maxs][maxn];
int st[maxn];
int s[maxn],n,k;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
ll solve(){
int maxst=(1<<n)-1;
for(int i=2;i<=n;i++) st[i]=st[i-1]<<1;
for(int i=1;i<=n;i++) f[st[i]][i]=1;
for(int i=1;i<=maxst;i++)
for(int j=1;j<=n;j++)
if(i&st[j])
for(int p=1;p<=n;p++)
if(!(i&st[p]) && abs(s[j]-s[p])>k)
f[i+st[p]][p]+=f[i][j];
ll ans=0;
for(int i=1;i<=n;i++) ans+=f[maxst][i];
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("mixed.in","r",stdin);
freopen("mixed.out","w",stdout);
#endif
fcin(n);fcin(k); st[1]=1;
for(int i=1;i<=n;i++) fcin(s[i]);
printf("%lld",solve());
return 0;
}