Time Limit: 3 second

Memory Limit: 256 MB

【问题描述】

有这么一个游戏： 写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：

3 1 2 4

4 3 6

7 9

16

最后得到16这样一个数字。

现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]，为1～N的一个排列。若答案有多种可能，则输出字典序最小的那一个。

【数据规模】

对于40%的数据，n≤7；

对于80%的数据，n≤10；

对于100%的数据，n≤12，sum≤12345，且保证一定有解。

【输入格式】

输入文件bds.in的第1行为两个正整数n，sum。

【输出格式】

输出文件bds.out包括1行，对于每个询问输出答案。

【输入样例1】

4 16

【输出样例1】

3 1 2 4

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t030

【题解】



可以画一画样例



注意观察一下最后的答案;

发现其实最后答案=3*1+3*2+1*3+1*4

可以看到第一行的各项的系数是分别是C[3][0],C[3][1],C[3][2],C[3][3];

发现规律!

最后的答案就为

设第一行的第i列元素为a[i]

则最后一行的那一个元素为∑a[i]*C[n-1][i-1]

则我们先预处理出组合数(C[i][j] = C[i-1][j-1]+C[i-1][j]）

然后枚举第一行的各个元素分别是什么;

然后O(1)得到最后一行的那唯一一个元素;

看看是不是所要求的sum;

因为这个∑符号里面的各项都是正数,所以可以写一个剪枝;

如果前i项的∑a[i]*C[n-1][i]>sum,则直接剪掉;就不用再等到i=n的时候再判断了;

sum比较小;这个剪枝还是很强力的;



【完整代码】

#include <cstdio>

#include <cstdlib>

#define rei(x) scanf("%d",&x)

#define rep1(i,x,y) for (int i = x;i <= y;i++)

const int MAXN = 15;

int n,sum,a[MAXN];

int c[MAXN][MAXN];

bool bo[MAXN];

void dfs(int x,int now)

{

    if (now > sum)

        return;

    if (x>n)

    {

        if (now==sum)

        {

            rep1(i,1,n)

            {

                printf("%d",a[i]);

                if (i==n)

                    puts("");

                else

                    putchar(' ');

            }

            exit(0);

        }

        return;

    }

    rep1(i,1,n)

    if (!bo[i])

        {

            bo[i] = true;

            a[x] = i;

            dfs(x+1,now+c[n-1][x-1]*a[x]);

            bo[i] = false;

        }

}

int main()

{

    rep1(i,1,13)

        c[i][i] = c[i][0] = 1;

    rep1(i,1,13)

        rep1(j,1,i-1)

            c[i][j] = c[i-1][j-1]+c[i-1][j];

    rei(n);rei(sum);

    if (n==1)

        puts("1");

    else

        dfs(1,0);

    return 0;

}