【noip模拟赛4】Matrix67的派对 dfs

描述

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

输出样例 1

2

一开始的想法是枚举全排列 然后遍历判断  
然后wa三个点
想到有可能有重复的数值  所以进行唯一化处理
最后还是wa一个点

#include<bits/stdc++.h>

using namespace std;

//input

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define LL long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

int main()

{

    int n,k;

    RII(n,k);

    double a[];

    rep(i,,n)

    {

        scanf("%lf",&a[i]);

        a[i]=a[i]+i*0.00000000000001;//

    }

    int cnt=;

    sort(a+,a++n);

    double first=a[];

    do

    {

        int ok=;

        rep(i,,n-)

        if(fabs(a[i]-a[i+])-k>1e-){ok=;break;}

        if(fabs(a[]-a[n])-k>1e-  )ok=;

        if(ok)cnt++;

    }

    while(next_permutation(a+,a++n)&&a[]==first);

   cout<<cnt;

}

更加简便的方法而且可以有效防止重复：因为是小数据直接搜索即可

#include<bits/stdc++.h>

using namespace std;

//input

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define LL long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

int vis[];

int first;

int a[];

int n,k,cnt;

void dfs(int num,int last)

{

    if(num==n&&abs(first-last)<=k)

    {

        cnt++;

        return;

    }

    rep(i,,n)

    if(!vis[i]&&abs(last-a[i])<=k)

    {

        vis[i]=;

        dfs(num+,a[i]);

        vis[i]=;

    }

   return;

}

int main()

{

    RII(n,k);

    rep(i,,n)

    RI(a[i]);

    cnt=;

        CLR(vis,);

        first=a[];

        vis[]=;

        dfs(,a[]);

    cout<<cnt;

    return ;

}