传送门
状压dp入门题。
按照题意建一个图。
要求的就是合法的链的总数。
直接f[i][j]f[i][j]f[i][j]表示当前状态为jjj，下一位要跟iii连起来的方案数。
然后从没被选并且跟iii连通的点转移就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20;
bool tran[N][N];
int n,K,up,s[N];
ll f[N][1<<16];
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline ll dfs(int pos,int sta){
if(~f[pos][sta])return f[pos][sta];
if(sta+1==up)return f[pos][sta]=1;
f[pos][sta]=0;
for(int i=1;i<=n;++i){
if(!tran[i][pos]||((sta>>(i-1))&1))continue;
f[pos][sta]+=dfs(i,sta|(1<<(i-1)));
}
return f[pos][sta];
}
int main(){
memset(f,-1,sizeof(f)),n=read(),K=read(),up=1<<n;
for(int i=1;i<=n;++i){
s[i]=read();
for(int j=1;j<i;++j)if(abs(s[i]-s[j])>K)tran[i][j]=tran[j][i]=1;
tran[i][0]=tran[0][i]=1;
}
cout<<dfs(0,0);
return 0;
}