【noip模拟赛4】Matrix67的派对
描述
Matrix67发现身高接近的人似乎更合得来。Matrix67举办的派对共有N(1<=N<=10)个人参加，Matrix67需要把他们安排在圆桌上。Matrix67的安排原则是，圆桌上任意两个相邻人的身高之差不能超过K。请告诉Matrix67他共有多少种安排方法。
输入
第一行输入两个用空格隔开的数N和K，其中1<=N<=10，1<=K<=1 000 000。
第二行到第N+1行每行输入一个人的身高值。所有人的身高都是不超过1 000 000的正整数
输出
输出符合要求的安排总数
输入样例 1
4 10
2
16
6
10
输出样例 1
2 做法：
用dfs试每一条路，记录一个步数step，当step==n，切该点和起点差距小于k时，答案就累计一个。
开3个数组：
1 pre 记录 step-1 时，是哪个点，用来与step时的各个数比较判断能否做一起。
2 flag 在试没一条路时，用flag标记每一条路，防止死循环，这条路探完后，重置为0。
3 high 记录每个人的高。 注意：有特解 当n=1时，ans 应为1。
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=;
int high[maxn],pre[maxn];
int n,k,ans;
bool flag[maxn]; void dfs(int step)
{ for(int i=;i<=n;i++)
{
if(!flag[i]&&abs(high[i]-high[pre[step-]])<=k)
{
flag[i]=;
pre[step]=i;
if(step==n&&abs(high[pre[step]]-high[])<=k)
{
ans++;
}
else
dfs(step+);
flag[i]=;
}
}
} int main(void)
{
// freopen("input.txt","r",stdin);
cin>>n>>k;
for(int i=;i<=n;i++)
{
cin>>high[i];
}
if(n==)
ans=;
else
{
ans=;
flag[]=;
pre[]=;
dfs();
}
cout<<ans<<endl;
return ;
}