题目大意：

有这么一个游戏：

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

3 1 2 4

4 3 6

7 9

16

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

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

---

思路：

注：这道题不是那道简单的DP数字金字塔！

虽然这道题还是很简单。。。

我们观察一下，就可以发现：

n=2,最终得a+b

n=3,得a+2b+c

n=4,得a+3b+3c+d

n=5,得a+4b+6c+4d+e

每个字母的系数为杨辉三角第行的数！

、

那么这道题的方法就很明确了：

1.由于n<=13，所以可以暴力求杨辉三角。

2.DFS，搜索。

---

代码：

#include 
    
     #include 
     
      using namespace std;int n,ok,m,a[101][101],o[101],t[101];void dfs(int x,int k)  //DFS搜索{    if (x>n)    {        if (k==m)  //和正好为m        {            for (int i=1;i<=n;i++) printf("%d ",o[i]);              ok=1;        }        return;    }    if (k>m) return;  //剪枝    for (int i=1;i<=n;i++)    {        if (t[i]==0)  //没有用过这个数        {           t[i]=1;           o[x]=i;           dfs(x+1,k+i*a[n][x]);           t[i]=0;           o[x]=0;        }        if (ok==1) return;    } }int main(){    scanf("%d%d",&n,&m);    a[0][1]=1;    for (int i=1;i<=n;i++)      for (int j=1;j<=i;j++)       a[i][j]=a[i-1][j]+a[i-1][j-1];  //求杨辉三角    dfs(1,0);         return 0;}