MIXUP2 - Đàn bò hỗn loạn

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   17
typedef long long ll;
ll f[MAX][1<<MAX];
int n,k;
int a[MAX];
int lg2[1<<MAX];
int iabs(const int &x) {
	if (x<0) return (-x); else return (x);
}
void init(void) {
	scanf("%d",&n);
	scanf("%d",&k);
	int i;
	for (i=0;i<n;i=i+1) scanf("%d",&a[i]);
	for (i=0;i<MAX;i=i+1) lg2[1<<i]=i;
}
void optimize(void) {
	int i,j,s,t;
	for (i=0;i<n;i=i+1)
		f[i][(1<<n)-1-(1<<i)]=1;
	for (j=(1<<n)-1;j>=0;j=j-1)
		for (i=0;i<n;i=i+1) {
			if ((j|(1<<i))==j) continue;
			s=j;
			while (s>0) {
				t=lg2[s&(-s)];
				if (abs(a[t]-a[i])>k) f[t][j-(1<<t)]+=f[i][j];				
				s=s-(1<<t);
			}
		}
	ll res=0;
	for (i=0;i<n;i=i+1) res+=f[i][0];
	printf("%lld",res);
}
int main(void) {
	init();
	optimize();
	return 0;
}

Download