题目链接：https://www.luogu.org/problemnew/show/P1118
题意：
1~n的一个排列，相邻的两项加起来得到下一行。
现在给定最后一行的数字，问最初的1~n的排列是什么。
思路：
next_permutation大法好。但是要注意剪枝。
首先要发现最后一行这个数系数的规律是一个杨辉三角。
先处理出这个系数。
然后排列。
如果我们在加到前i项的时候发现他已经比结果大了，那么后面不管怎么排列都是没有用的，要跳过。
怎么跳过呢，这里还挺tricky的【要学会！】
用sort对后面几个数从大到小排序就行了，因为本身next_permutation就是按照“字典序”来排的
这里要注意用的是do...while【竟然这年头还真有用do...while的】
因为不然第一个1234....n这个排列没有被考虑到。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<queue> 10 11 using namespace std; 12 typedef long long LL; 13 typedef pair<int, int> pr; 14 15 int n, sum; 16 int num[15]; 17 int xishu[15][15]; 18 19 bool cmp(int a, int b) 20 { 21 return a > b; 22 } 23 24 int main() 25 { 26 // LL res = 1; 27 // for(int i = 1; i <= 12; i++){ 28 // res *= i; 29 // } 30 // printf("%lld\n", res); 31 scanf("%d%d", &n, &sum); 32 for(int i = 1; i <= n; i++){ 33 num[i] = i; 34 } 35 xishu[1][1] = 1; 36 for(int i = 2; i <= n; i++){ 37 for(int j = 1; j <= i; j++){ 38 xishu[i][j] = xishu[i - 1][j - 1] + xishu[i - 1][j]; 39 } 40 } 41 42 do{ 43 int ans = 0; 44 bool flag = true; 45 for(int i = 1; i <= n; i++){ 46 ans += xishu[n][i] * num[i]; 47 if(ans > sum){ 48 flag = false; 49 sort(num + i, num + 1 + n, cmp); 50 break; 51 } 52 } 53 if(ans == sum && flag){ 54 printf("%d", num[1]); 55 for(int i = 2; i <= n; i++){ 56 printf(" %d", num[i]); 57 } 58 printf("\n"); 59 break; 60 } 61 }while(next_permutation(num + 1, num + 1 + n)); 62 63 return 0; 64 }
原文：https://www.cnblogs.com/wyboooo/p/10355602.html