输入n个数字和一个数字k 求任意两个相邻数字之差都大于k的排列数 n≤16
思路是状压 但我标程看不懂QAQ求大佬解释
#include <cstdio>
using namespace std;
typedef long long ll;
inline int abss(int x){return x<0?-x:x;}
int n,K,a[16];
ll res(0),f[1<<16][16];//f[i][j]表示状态为i,选了前j个数的情况数 这是我唯一看懂的一点QAQ
int main(){
scanf("%d%d",&n,&K);
for(int i=0;i<n;++i){
scanf("%d",a+i);
f[1<<i][i]=1;
}
for(int i=1;i<(1<<n);++i)
for(int j=0;j<n;++j)
if(i&(1<<j))
for(int k=0;k<n;++k)
if(j!=k && (i&(1<<k)) && abss(a[j]-a[k])>K)
f[i][j]+=f[i^(1<<j)][k];
for(int i=0;i<n;++i)
res+=f[(1<<n)-1][i];
printf("%lld\n",res);
fclose(stdin);
fclose(stdout);
return 0;
}