1851: 【贪心】扇区填数
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
有一个圆，当输入一个整数n(1≤n≤6)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。
向各个扇区放入数之后，你可以从单个扇区中选出—个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列，：1，2，3，…，i，你的任务是使i尽可能地大。
输入
只一个整数n(1<＝n<＝6)。
输出
第一行是最大的i，接下来的几行是所有能达到最大i的填法。
由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从1，开始输出(因为连续数里要有1，所以所填的数中肯定有1)。
样例输入
1样例输出
1
1提示
假设圆已经被分成了n个扇区，并且已经在这n个扇区中填好了数字，先来看看填好数字后最多有多少种选择连续的数字并求和的方法，以N＝4为例：
单独选一个，有n种即1、2、3、4；
选择相邻两个也有n种即12、23、34、41
选择相邻三个也有n种即123、234、341、412；
选择相邻四个只有一种即1234。
总共有n*(n-1)+1种，当n=4时有13种。
如果每一种选择所求的和都不同，那么能够构成的最多有n*(n-1)+1个不同的数。我们当然希望能够达到的最大的连续数就是从1到n*(n-1)+1了，如N=4时就是1到13。
现在的问题是如何保证这n*(n-1)+1个数就是从1到n*(n-1)+1。在填数时首先填1，接下来的n-1个数都保证不同且最小为2，再看其他的取相邻的多个数的情况了。在n<＝6的情况下都能满足这个要求，对于n>6时就不一定了。
从这种最优策略出发，再结合回溯法找出所有可能的情况。