【状压DP】bzoj1231 [Usaco2008 Nov]mixup2 混乱的奶牛

f(i,j)表示当前牛的集合为i，最后一个牛为j时的方案数。

f(i∪{k},k)+=f(i,j)　　//k∉i&&j∈i

init:f({i},i)=1　　//0<=i<n

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 17
int n,m,a[N];
ll ans,f[(1<<N)+1][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) scanf("%d",&a[i]);
	for(int i=0;i<n;++i) f[1<<i][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[k]-a[j])>m)//枚举不在集合中的一个元素
			  f[i|(1<<k)][k]+=f[i][j];
	for(int i=0;i<n;++i) ans+=f[(1<<n)-1][i];
	printf("%lld
",ans);
	return 0;
}