题目链接：传送门

Description

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

Input

第1行：一个整数n（n＜30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

Output

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。

Solution

因为题目给出了中序遍历，且一棵子树在中序遍历中一定是一段连续的区间，因此对子树的计算便可转化为对区间的计算。

因此这道题就可以转化为区间DP

我们设F[i][j]F[i][j]表示在区间[i,j]中的最大加分，也就是从i到j组成的子树的最大加分，

那么便有区间DP的套路: F[i][j]=max(F[i][j],F[i][k−1]∗F[k+1][j]+F[k][k])F[i][j]=\max(F[i][j],F[i][k-1] * F[k+1][j]+F[k][k])

当然当k==i || k==j时我们要特殊处理下

至于输出前序遍历的话，我们可以开一个root[][]数组表示i到j的根，输出时递归处理即可

Code

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
#include<bits/stdc++.h>
using namespace std;
int n;
int a[35],f[50][50],root[50][50];
inline void print(int l,int r){
    if(l==r){
        printf("%d ",l);
        return ;
    }   
    if(r-l==1){
        if(root[l][r]==l)printf("%d %d ",l,r);
        else printf("%d ",r,l);
        return ;
    }
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i][i]=a[i];
    for(int l=1;l<n;l++)
        for(int i=1;i<=n-l;i++){
            int j=i+l;
            for(int k=i;k<=j;k++){
                int a1=f[i+1][j]+f[i][i],a2=f[i][j-1]+f[j][j],a3=f[i][k-1]*f[k+1][j]+f[k][k];
                if(k==i && a1>f[i][j])
                    f[i][j]=a1,root[i][j]=i;
                else if(k==j && a2>f[i][j])
                    f[i][j]=a2,root[i][j]=j;
                else if(a3>f[i][j])
                    f[i][j]=a3,root[i][j]=k;
            }
            //cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }
    cout<<f[1][n]<<endl;
    print(1,n);
    return 0;
}