挑战-搜索

题意:

给一个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;
}
05-18 11:10