自动搬运

查看原文

来自洛谷，原作者为

	asuldb 哭晕了喵

搬运于2025-08-24 21:43:24，当前版本为作者最后更新于2018-05-22 15:22:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们能够一眼看到4 <= N <= 16，那么就是它了，我们要压缩的状态就是它了

那么之后能我们用这个状态表示什么呢，我们要表示的显然是每只奶牛是否在队伍中 比如说10吧，转成二进制后就是1010，这就代表了第一只和第三只奶牛已经在队伍中，而第二只和第四只还没有在队伍中

那么就有一些状态可以初始化了，对于那些只有一只奶牛在队伍中，即某个状态转为二进制后只有一个1的状态我们就可以初始化为1

但是我们要判断的是这个队伍是否“混乱”，混乱的定义是：相邻奶牛的编号之差均超过K，于是我们在由一个状态得到一个新状态时一定要去判断这个原状态加上那个我们新添加到队伍末尾的那只奶牛后是否还是混乱的 那么我们要怎么做呢 显然我们的dp数组里存的不止是状态了，还应该存一个能帮助我们判断的东西 那就想想我们一旦新在队伍末尾加入一个奶牛后是怎么判断的呢

很显然只要新加入的这只奶牛和原本队尾那只奶牛的编号差大于k就可以使队伍继续混乱下去了，因为我们必须保证那个原来的状态是合法的，也就是说原来的那个队伍是混乱的

于是我们的dp数组就呼之欲出了

我们设 f[i][j]表示以第i只奶牛为结尾的状态为j的队伍混乱的方案数是多少

而我们怎么转移状态呢，我们知道对于每一个状态都有很多结尾，于是我们用两个循环，一个枚举状态，一个枚举结尾的奶牛

当然我们还需要判断这个情况是否存在，比如说f[2][10]吧，它表示10这个状态也就是1010，以第二只奶牛为结尾的方案数，这种情况显然是不存在的，因为在1010这个状态中第二只奶牛根本没有被选择，根本不可能成为结尾，所以对于这种情况我们需要进行判断

在最后我们统计答案的时候要把枚举各种奶牛作为结尾且所有奶牛均被选择的情况

于是就很简单了

之后就是代码了

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define int long long
#define maxn 17
using namespace std;
int k;
int n,a[maxn],f[maxn][1<<maxn];
inline int read()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	  x=(x<<3)+(x<<1)+c-48,c=getchar();
	return x;
}
signed main()
{
	n=read();
	k=read();
	for(re int i=1;i<=n;i++)
		a[i]=read();
	for(re int i=1;i<=n;i++)
		f[i][1<<(n-i)]=1;
	for(re int i=1;i<(1<<n);i++)//枚举状态 
	for(re int j=1;j<=n;j++)//枚举结尾奶牛 
	{
		if(f[j][i]) continue;
		if(!(i&(1<<(n-j)))) continue;
		//判断这种情况是否存在 
		int m=i^(1<<(n-j));
		//得到一个没有选择当前结尾奶牛j的状态 
		for(re int g=1;g<=n;g++)
		//枚举这个状态m的结尾 
		{
			if(g==j) continue;
			if(a[j]-a[g]>k||a[g]-a[j]>k) f[j][i]+=f[g][m];
			//符合混乱的条件，进行转移 
		}
	}
	int ans=0;
	for(re int i=1;i<=n;i++)
	ans+=f[i][(1<<n)-1];
	cout<<ans<<endl;
	return 0;
}