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.

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

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

1
2
3
4
5
4 1 
3 
4 
2 
1

Sample Output

1
2

分析

这道题考试时写了回溯，结果作死的把每种方案详细的输出来了导致部分分也没有了，后来才知道正解应是状压 DP

先看看开始写的错误 DP：$f[i][j]=\sum_{p=1}^{n}f[i-1][k]\;\;\;(abs(s[j]-s[p])>k)$

这里的 $i$ 表示行数，$j$ 表示最后放第 $j$ 头牛，边界情况为 $f[1][i]=1\;\;\;(i\in[1,\;n])$

这样写的话明显会计算到重复的情况（这里指隔一位出现同一头牛），而且怎么改也改不对。。。

但是最初的思路是有用的，状压 DP 的思路与此已经很相近了，不同的是，用类似 TSP问题 的思路

设 $f[i][j]$ 表示当前放置的状态为二进制数 $i$ 的情况下，最后放的是第 $j$ 头奶牛的方案数，新的状态转移方程为：$f[i][j]=\sum^{n}_{p=1}f[i’][p]\;\;\;(i’=i-2^j,\;j\notin i,\;p\in i’,\;abs(s[j]-s[p])>k)$

当然也可以写成：$f[i’][p]=\sum^n_{p=1}f[i][j]\;\;\;(i’=i+2^p,\;j\in i,\;p\notin i,\;abs(s[j]-s[p])>k)$

这里的 $i$ 表示的是放置状态的集合，用 i & (1<<j) 可以判断 $j$ 是否处于 $i$ 中（$p$ 同理）

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}