原题链接

ACwing

思路

如果只知道一棵树的中序遍历，无法确定这一棵树的构造；不过，我们可以通过假定各个子树的根，从中序遍历中构造出一颗符合条件的树（有多少种可能实际上也可以通过动态规划求出）。

如果我们选定了一个根，其子树的最大值与该根无关，换而言之，问题具有最优子结构。自然而然的，我们应该使用一个中序遍历的区间作为状态（唯一确定一个最大值），原问题实际上就变成了一个区间DP 问题。

由于此处需要我们重构一棵树，所以保存每一个区间的最优节点，这样就可以通过dfs还原树。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

const int N = 40;
int dp[N][N];
int best[N][N];
int val[N];

int solve(int arrlen){
    memset(dp,0,sizeof dp);
    
    for (int len =1;len<=arrlen;len++){
        for(int i=1;i+len-1<=arrlen;i++){
            int j = i+len-1;
            if(len==1){
                dp[i][i] = val[i];
                continue;
            }
            
            int maxv = -1;
            for(int k=i;k<=j;k++){
                int root = val[k];
                int left=1;
                if(k-1>=i)left = dp[i][k-1];
                int right =1;
                if(k+1<=j)right = dp[k+1][j];
                int tem = root + left*right;
                
                if(tem>maxv){
                    best[i][j] = k;
                    maxv = tem;
                }
            }
            dp[i][j] = maxv;
        }
    }
    return dp[1][arrlen];
}

void build_tree(int l, int r,vector<int>&q){
    if(l>r)return;
    
    if(l==r){
        q.push_back(l);
        return;
    }
    
    int best_root = best[l][r];
    q.push_back(best_root);
    build_tree(l,best_root-1,q);
    build_tree(best_root+1,r,q);
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>val[i];
    vector<int>pre_order;
    cout<<solve(n)<<endl;
    build_tree(1,n,pre_order);
    for(int i=0;i<pre_order.size();i++){
        if(i)cout<<" ";
        cout<<pre_order[i];
    }
    return 0;
}