Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
有这么一个游戏： 写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：
3 1 2 4
4 3 6
7 9
16
最后得到16这样一个数字。 现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]，为1～N的一个排列。若答案有多种可能，则输出字典序最小的那一个。
【输入格式】
输入文件bds.in的第1行为两个正整数n，sum。
【输出格式】
输出文件bds.out包括1行，为字典序最小的那个答案。
【数据规模】
对于40%的数据，n≤7； 对于80%的数据，n≤10； 对于100%的数据，n≤12，sum≤12345，且保证一定有解。
Sample Input1
4 16
Sample Output1
3 1 2 4【题解】
从最下面往上推
a上面的b和c都会被加1次。
再往上则d会因为d+e=b 加1次。
e会因为d+e和e+f加2次。
f会因为e+f加一次。
所以d用了1次，e用了2次，f用了1次。
再往上。
g会因为g+h=d加一次
h会因为g+h加一次，还会因为h+i==e加两次。因为e被加了两次。
同理i因为h+i==e加了两次因为i+j==f加了一次。
j因为i+j==f加了一次。
综上g,h,i,j分别加了1,3,3,1次。
可以看出来是杨辉三角了。
知道了每个序列中的每一个元素最后会加几次。就不用一层一层地算下来了。
以后只要枚举完一个序列。直接用那些1,3,3,1这样的数字作为系数。乘上序列中的相应位置上的数字就可以了。
注意是1-n的全排列。
【代码】
#include <cstdio>
#include <cstring>
#include <stdlib.h>
int n,sum;
int yanghui[20][20]= {0},what[20];
bool bo[20];
void input_data()
{
memset(bo,0,sizeof(bo)); //每个数字一开始都没有被用过。
scanf("%d%d",&n,&sum);
yanghui[1][1] = 1;
for (int i = 2;i <= n;i++) //处理出第n层的杨辉三角
for (int j = 1;j <= i;j++)
yanghui[i][j] = yanghui[i-1][j-1]+yanghui[i-1][j];
}
void sear_ch(int next,int now) //要找的下一个是next,当前累加的值为now
{
if (now > sum) //如果大于sum了则剪枝
return;
if (next == n+1) //如果找完n个数字则判断是否和sum相同。
{
if (now == sum)
{
for (int i = 1;i <=n-1;i++) //输出答案。
printf("%d ",what[i]);
printf("%d",what[n]);
exit(0);
}
return;
}
for (int i = 1;i <= n;i++) //继续枚举数字放在next的位置
if (!bo[i]) //没有用过
{
bo[i] = true; //记录用过
what[next] = i; //记录用了什么数字
sear_ch(next+1,now+yanghui[n][next]*i); //乘上相应的系数即可。
bo[i] = false;
}
}
void get_ans()
{
for (int i = 1;i <= n;i++) i//这是第一个数字。
if (!bo[i])
{
bo[i] = true; //记录i这个数字已经被使用过了。
what[1] = i; //记录这个位置放什么
sear_ch(2,yanghui[n][1]*i);//进入递归。
bo[i] = false;
}
}
int main()
{
input_data();
get_ans();
return 0;
}