洛谷P1118 数字三角形

题目描述

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

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

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

题目解析

这道题其实就是杨辉三角加搜索。下面来分析一下：
假设n为1，全排列只有1个，为1

假设n为2，选择1-2的一个全排列，为2,1。

假设现在n为3，选择1-3其中一个全排列，为2，3，1。

假设现在n为4，我们随便选择1-4的其中一个全排列，为1，2，3，4。

到这个我们就可以发现规律了，随着n的变化，n的全排列前的系数也在发生变化，无论是个数或者数值，现在我将这些系数整理一下。

发现了吧，这些系数随着n的变化而变化，最终构成了一个杨辉三角，那么知道这个规律后，我们来解题就简单了，就是一个全排列+杨辉三角的事情了。

构造杨辉三角数组

  for(int i = 1; i <= n; i ++){
        ptri[i][1] = ptri[i][i] = 1;
    }
    for(int i = 3; i <= n; i ++){
        for(int j = 2; j <= n; j ++){
            ptri[i][j] = ptri[i-1][j-1]+ptri[i-1][j];
        }
    }

剩下的就是全排列的事情了，在这边就不多做解释了。

代码实现

#include <iostream>
const int size = 15;
using namespace std;

int ptri[size][size];
int arr[size];
bool book[size],flag;
int n,sum;

void dfs(int cur,int val){
    if(val > sum || (val == sum && cur <= n) || flag){
        return ;
    }
    if(cur == n+1){
        if(val == sum){
            for(int i = 1; i <= n; i ++){
                cout << arr[i] << " ";
            }
            cout << endl;
            flag = true;
        }
    }
    for(int i = 1; i <= n; i ++){
        if(!book[i]){
            arr[cur] = i;
            book[i] = true;
            dfs(cur+1,val+ptri[n][cur]*i);
            book[i] = false;
        }
    }
}

int main() {
    cin >> n >> sum;
    for(int i = 1; i <= n; i ++){
        ptri[i][1] = ptri[i][i] = 1;
    }
    for(int i = 3; i <= n; i ++){
        for(int j = 2; j <= n; j ++){
            ptri[i][j] = ptri[i-1][j-1]+ptri[i-1][j];
        }
    }
    dfs(1,0);
    return 0;
}