挑战-搜索

题意：

给一个n和sum,代表n层的杨辉三角，然后给一个和，问最低层的数字情况。

思路：

①：预处理一个底层对于和的系数数组，

sum = 0Cn-1*num[1] + 1Cn-1*num[2] +…+ n-1Cn-1*num[n];

②：因为底层就是1-n直接暴搜…即可…

贴一发挫code………

#include<cstdio>

#include<map>

#include<queue>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define eps 1e-8

typedef __int64 LL;

// 杨辉三角第n层第k个数记为Ckn

// 那么=n!/[k!(n-k)!]=n * (n – 1)…*(n – k + 1) / k!

//sum = 0Cn-1*num[0] + 1Cn-1*num[1] +``+ n-1Cn-1*num[n-1]

const int N=12;

int c[N];

int num,n;

bool vis[N];

int d[N],flag;

int cal(int x)

{

    int i=1,ans=1;

    int t=n-1;

    while(i<=x)

    {

        ans=ans*t/i;

        t--;i++;

    }

    return ans;

}

void dfs(int x,int sum)

{

    if(flag) return;

    if(sum>num) return;

    if(x==n)

    {

        if(sum==num&&!flag)

        {

            flag=1;

            for(int i=0;i<n;i++)

            {

                if(i) printf(" ");

                printf("%d",d[i]);

            }

            flag=1;

        }

        return;

    }

    for(int i=1;i<=n;i++)

    {

        if(!vis[i])

        {

            d[x]=i;

            vis[i]=1;

            dfs(x+1,sum+i*c[x+1]);

            vis[i]=0;

        }

    }

}

int main()

{

    scanf("%d%d",&n,&num);

    for(int i=1;i<=n;i++)

        c[i]=cal(i-1);

//    for(int i=1;i<=n;i++)

//        printf("%d ",c[i]);

    memset(vis,0,sizeof(vis));

    flag=0;

    dfs(0,0);

    return 0;

}