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