题目描述
有这么一个游戏：
写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：
3 1 2 4
4 3 6
7 9 16 最后得到16这样一个数字。
现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]，为1～N的一个排列。若答案有多种可能，则输出字典序最小的那一个。
[color=red]管理员注：本题描述有误，这里字典序指的是1，2，3，4，5，6，7，8，9，10，11，12
而不是1，10，11，12，2，3，4，5，6，7，8，9[/color]
输入输出格式
输入格式：
两个正整数n，sum。
输出格式：
输出包括1行，为字典序最小的那个答案。
当无解的时候，请什么也不输出。（好奇葩啊）
输入输出样例
输入样例#1：
4 16
输出样例#1：
3 1 2 4
说明
对于40%的数据，n≤7；
对于80%的数据，n≤10；
对于100%的数据，n≤12，sum≤12345。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 int xvlie[1005],used[1005],yanghui[55][55]; 8 int des,n,note=0; 9 ll sum=0; 10 void make_yanghui(){ 11 for(int i=1;i<=13;i++){ 12 yanghui[i][1]=yanghui[i][i]=1; 13 } 14 for(int i=2;i<=13;i++){ 15 for(int j=2;j<i;j++){ 16 yanghui[i][j]=yanghui[i-1][j]+yanghui[i-1][j-1]; 17 } 18 } 19 20 } 21 22 void search(int k){ 23 if(note==1) return; 24 if(sum>des) return; 25 if(k==n+1&&sum==des) { 26 note=1; 27 for(int i=1;i<=n;i++){ 28 printf("%d ",xvlie[i]); 29 } 30 puts(""); 31 return ; 32 } 33 34 for(int i=1;i<=n;i++){ 35 if(used[i]==1) continue; 36 37 used[i]=1; 38 xvlie[k]=i; 39 40 sum+=yanghui[n][k]*i; 41 42 search(k+1); 43 44 sum-=yanghui[n][k]*i; 45 used[i]=0; 46 xvlie[k]=0; 47 } 48 } 49 50 int main(){ 51 // freopen("01.in","r",stdin); 52 scanf("%d%d",&n,&des); 53 make_yanghui(); 54 search(1); 55 56 return 0; 57 }这种问题肯定有规律，算一下就会发现对应杨辉三角形
虽然n比较小但是也要优化一下24行没加的话会Tle
40行，44行就是边加边算，不用每次都从头再来一次