挑战-搜索
题意:
给一个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;
}