题解 | #加分二叉树#

package main

import (
	"fmt"
)

func main() {
	var n int32
	var cost [50]int32
	var dp, roots [50][50]int32
	fmt.Scan(&n)
	for i := int32(1); i <= n; i++ {
		fmt.Scan(&cost[i])
		dp[i][i] = cost[i]
		roots[i][i] = i
	}
	for l := int32(2); l <= n; l++ {
		for i := int32(1); i <= n && i+l-1 <= n; i++ {
			j := i + l - 1
			for k := i; k <= j; k++ {
				left, right := int32(1), int32(1)
				if k != i {
					left = dp[i][k-1]
				}
				if j != k {
					right = dp[k+1][j]
				}
				score := cost[k] + left*right
				if dp[i][j] < score {
					dp[i][j] = score
					roots[i][j] = k
				}
			}
		}
	}
	//    for i:=n; i>0; i-- {
	//     for j:= i+1; j <=n; j++ {
	//         for k:=i; k <=j; k++ {
	//             score := cost[k]
	//             if k -i > 0 && j-k > 0{
	//                 score += dp[i][k-1]*dp[k+1][j]
	//             } else if k -i > 0{
	//                 score += dp[i][k-1]
	//             } else if j-k > 0{
	//                 score += dp[k+1][j]
	//             }
	//             if dp[i][j] < score {
	//                 dp[i][j] = score
	//                 roots[i][j] = k
	//             }
	//         }
	//     }
	//    }

	list := make([]int32, 0, n)
	var dfs func(left, right int32)
	dfs = func(left, right int32) {
		list = append(list, roots[left][right])
		if left >= right {
			return
		}
		if left < roots[left][right] {
			dfs(left, roots[left][right]-1)
		}
		if roots[left][right] < right {
			dfs(roots[left][right]+1, right)
		}

	}
	dfs(1, n)
	fmt.Println(dp[1][n])
	for i := int32(0); i < n; i++ {
		if i < n-1 {
			fmt.Printf("%d ", list[i])
		} else {
			fmt.Println(list[i])
		}
	}
}