设一个 nn 个节点的二叉树 tree 的中序遍历为（1,2,3,…,n1,2,3,…,n），其中数字 1,2,3,…,n1,2,3,…,n 为节点编号。
每个节点都有一个分数（均为正整数），记第 ii 个节点的分数为 didi，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：
subtree的左子树的加分 ×× subtree的右子树的加分 ＋＋ subtree的根的分数
若某个子树为空，规定其加分为 11。
叶子的加分就是叶节点本身的分数，不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n1,2,3,…,n）且加分最高的二叉树 tree。
要求输出：
（1）tree的最高加分
（2）tree的前序遍历

输入格式

第 11 行：一个整数 nn，为节点个数。
第 22 行：nn 个用空格隔开的整数，为每个节点的分数（0<0<分数<100<100）。

输出格式

第 11 行：一个整数，为最高加分（结果不会超过int范围）。
第 22 行：nn 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围

n<30n<30

输入样例：

5 5 7 1 2 10

输出样例：

145 3 1 2 4 5

  1. //f[l,r] 表示中序遍历集合 l到r的最大分值集合
  2. //f[l,r] = max(f[l,r],f[l,k]*f[k+1,r] + w[i]);
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. const int N = 30;
  10. int n;
  11. int w[N];
  12. //g数组记录根节点是谁
  13. int f[N][N],g[N][N];
  15. //前序遍历
  16. void dfs (int l, int r) {
  17.     if (l > r) return;
  18.     int root = g[l][r];
  19.     cout << root << ' ';
  20.     dfs (l,root-1);
  21.     dfs (root+1,r);
  22. }
  24. int main() {
  25.     cin >> n;
  26.     for (int i = 1; i <= n; ++i) cin >> w[i];
  27.     for (int len = 1; len <= n; ++len) 
  28.         for (int l = 1; len + l - 1 <= n; ++l) {
  29.             int r = len + l - 1;
  30.             if (len == 1) {
  31.                 f[l][r] = w[l];
  32.                 g[l][r] = l;
  33.             } else {
  34.                 for (int k = l; k <= r; ++k) {
  35.                     int left = k == l ? 1 : f[l][k-1];
  36.                     int right = k == r ? 1 : f[k+1][r];
  37.                     int score = left * right + w[k];
  38.                     //保证都是最左边的更新，方便后面的字典序最小
  39.                     if (f[l][r] < score) {
  40.                         f[l][r] = score;
  41.                         g[l][r] = k;
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.     cout << f[1][n] << endl;
  47.     dfs(1,n);
  48.     return 0;
  49. }