poj 3187 Backward Digit Sums 枚举全排列

缘起

日常浪费生命 poj 3187 Backward Digit Sums

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
直接写中文了

Descriptions:

FJ 和 他的奶牛们在玩一个心理游戏。他们以某种方式写下1至N的数字（1<=N<=10）。 然后把相邻的数相加的到新的一行数。重复这一操作直至只剩一个数字。比如下面是N=4时的一种例子 

    3   1   2   4

      4   3   6

        7   9

         16
在FJ回来之前，奶牛们开始了一个更难的游戏：他们尝试根据最后结果找到开始的序列。这已超过了FJ的思考极限。 

写一个程序来帮助FJ吧
Input

N和最后的和
Output

满足要求的一行序列。若有多种情况，输出字典序最小的一种
Sample Input

4 16
Sample Output

3 1 2 4
Hint

样例解释 
这里还有其他可能的排列，若 3 2 1 4,但 3 1 2 4 是字典序最小的

枚举全排列. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n, sum;

int a[15],b[15];

bool ok()
{
	int k = n-1, len = n; // len是b的长度
	for (int i = 1; i<=n;i++)
	{
		b[i] = a[i];
	}
	while(k--)
	{
		for (int i = 1; i<len;i++)
		{
			b[i] = b[i]+b[i+1];
		}
		len--;
	}
	return b[1]==sum;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &sum);
	for (int i = 1; i<=n;i++)
	{
		a[i] = i;
	}
	do 
	{
		if (ok())
		{
			for (int i = 1; i<=n;i++)
			{
				printf("%d ",a[i]);
			}
			break; // 找到字典序最小的就不玩了
		}
	} while (next_permutation(a+1,a+n+1));
	return 0;
}
Status Accepted
Time 79ms
Memory 88kB
Length 685
Lang C++
Submitted 2019-08-23 22:29:47
Shared
RemoteRunId 20793677