479.-jia-fen-er-cha-shu.md

479. 加分二叉树

设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。

每个节点都有一个分数（均为正整数），记第i个节点的分数为didi，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：     

subtree的左子树的加分 × subtree的右子树的加分 ＋ subtree的根的分数 

若某个子树为空，规定其加分为1。叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。

要求输出： 

（1）tree的最高加分 

（2）tree的前序遍历

输入格式

第1行：一个整数n，为节点个数。 

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

输出格式

第1行：一个整数，为最高加分（结果不会超过int范围）。     

第2行：n个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围

n<30n<30

输入样例：

5
5 7 1 2 10

输出样例：

145
3 1 2 4 5

package main 

import (
    "fmt"
    )

func dfs(l, r int, g [][]int) {
    if l > r {return} 
    k := g[l][r];
    fmt.Printf("%d ", k + 1)
    dfs(l, k - 1 , g)
    dfs(k + 1, r, g)
}

func main(){
    
    var n int
    fmt.Scanf("%d", &n)
    A := make([]int, n)
    f := make([][]int,n)
    g := make([][]int,n)
    for i:=0; i < n; i ++ {
        fmt.Scanf("%d",&A[i])
        f[i] = make([]int,n)
        g[i] = make([]int,n)
    }
    
    for l:= 1 ; l <= len(A); l ++ {
        for i := 0 ; i + l - 1 < n ; i ++ {
            j := i + l - 1
            if l == 1{
                f[i][j] = A[i]
                g[i][j] = i
            }else {
                for k := i; k <= j ; k ++ {
                    var left = 1
                    if k != i{
                        left = f[i][k - 1]
                    }
                    var right = 1
                    if k != j {
                        right = f[k + 1][j]
                    }
                    var score = left * right + A[k]
                    if score > f[i][j]{
                        f[i][j] = score
                        g[i][j] = k
                    }
                }
            }
        }
    }
    fmt.Println(f[0][n- 1])
    dfs(0,n - 1, g)
    // f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值
    
}