FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this:
3 1 2 4 4 3 6 7 9 16Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ's mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.
输入
Line 1: Two space-separated integers: N and the final sum.
输出
Line 1: An ordering of the integers 1..N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.
样例输入
4 16
样例输出
3 1 2 4
提示
Explanation of the sample: There are other possible sequences, such as 3 2 1 4, but 3 1 2 4 is the lexicographically smallest.
题意：
我们把1-n这n个数的某个排列摆成一排，然后相邻两个数的和放到下一行，依此类推，形成一个三角形
3 1 2 4
4 3 6
7 9
16
给你n和最终得到的和k，求第一行的系列（字典序最小）
我们可以发现每个数字的计算次数是一个杨辉三角
1 1
1 2 1
1 3 3 1
1 4 6 4 1
......
所以我们只要枚举1-n的全排列，计算sum{now[i]*as(n-1,i)}是否为K就行了
#include#include #include #include #include #include #include using namespace std;typedef long long LL;const LL INF = 0xfffffff;const int maxn = 500;const LL MOD = 1e9+7;int ok[maxn], now[maxn], as[maxn][maxn], n, m, vis[maxn], flag; ///poj 3187void init(){ int i, j; as[0][0] = 1; for(i = 0; i <= 10; i++) { as[i][0] = as[i][i] = 1; for(j = 1; j < i; j++) as[i][j] = as[i-1][j] + as[i-1][j-1]; }}void dfs(int cnt){ if(flag )return ; if(cnt == n) { int ans = 0; for(int i = 0; i < n; i++) ans += as[n-1][i] * now[i]; if(ans == m) { flag = 1; for(int i = 0; i < n; i++) ok[i] = now[i]; } return ; } for(int i = 1; i <= n; i++) { if(!vis[i]) { vis[i] = 1; now[cnt++] = i; dfs(cnt); vis[i] = 0; cnt--; } } // return ; }int main(){ init(); while(~scanf("%d %d", &n, &m)) { flag = 0; memset(vis, 0, sizeof(vis)); dfs(0); printf("%d", ok[0]); for(int i = 1; i < n; i++) printf(" %d", ok[i]); printf("\n"); } return 0;}