1238. 加分二叉树

using namespace std;
const int maxn=35;
long long int score[maxn][maxn];
int vi[maxn];
int root[maxn][maxn];//用来存l-r之间的根节点
void printt(int l,int r)
{
        if(l>r) return;
        cout<<root[l][r]<<" ";
        printt(l,root[l][r]-1);
        printt(root[l][r]+1,r);
}
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;cin>>n;
        memset(score,0,sizeof(score));
        for(int i=1;i<=n;i++) cin>>vi[i];
        for(int i=1;i<=n;i++) root[i][i]=i;
        for(int i=1;i<=n;i++) score[i][i]=vi[i];
        for(int len=2;len<=n;len++){
                for(int i=1;i+len-1<=n;i++){
                        int j=i+len-1;
                        for(int k=i;k<=j;k++){
                                if(k==i){
                                        if(score[i][j]<score[k+1][j]+vi[k]){ 
                                                root[i][j]=k;
                                                score[i][j]=score[k+1][j]+vi[k];
                                        }
                                }
                                else if(k>i&&k<j){
                                        if(score[i][j]<score[i][k-1]*score[k+1][j]+vi[k]){ 
                                                root[i][j]=k;
                                                score[i][j]=score[i][k-1]*score[k+1][j]+vi[k];
                                        }
                                }
                                else if(k==j){
                                        if(score[i][j]<score[i][k-1]+vi[k]){
                                                root[i][j]=k;
                                                score[i][j]=score[i][k-1]+vi[k];
                                        }
                                }
                        }
                }
        }
        cout<<score[1][n]<<endl;
        printt(1,n);
}

#include "bits/stdc++.h"
using u32 = uint32_t;
using u64 = uint64_t;

struct DpRecord {
    u64 point = 0;
    std::vector<u32> preorder_traversal;
};

int main() {
    u32 n;
    std::cin >> n;
    std::vector<u32> node_points(n + 1);
    for (u32 i = 1; i <= n; ++i) {
        std::cin >> node_points[i];
    }
    std::vector dp(n + 1, std::vector<DpRecord>(n + 1));
    for (u32 i = 1; i <= n; ++i) {
        // Special case for leaves.
        dp[i][i].point = node_points[i];
        dp[i][i].preorder_traversal.push_back(i);
    }
    for (u32 span_size = 2; span_size <= n; ++span_size) {
        for (u32 i = 1, j = i - 1 + span_size; j <= n; ++i, ++j) {
            u32 root;
            u64 potential_max;
            { // Special case for borders.
                auto const kIAsRoot = dp[i + 1][j].point + node_points[i];
                auto const kJAsRoot = dp[i][j - 1].point + node_points[j];
                if (kIAsRoot < kJAsRoot) {
                    root = j;
                    potential_max = kJAsRoot;
                } else {
                    root = i;
                    potential_max = kIAsRoot;
                }
            }
            for (u32 k = i + 1; k < j; ++k) {
                auto const kPoint = dp[i][k - 1].point * dp[k + 1][j].point + node_points[k];
                if (potential_max < kPoint) {
                    potential_max = kPoint;
                    root = k;
                }
            }
            dp[i][j].point = potential_max;
            auto& vec = dp[i][j].preorder_traversal;
            vec.push_back(root);
            for (auto const id : dp[i][root - 1].preorder_traversal) {
                vec.push_back(id);
            }
            for (auto const id : dp[root + 1][j].preorder_traversal) {
                vec.push_back(id);
            }
        }
    }
    std::cout << dp[1][n].point << '\n';
    for (auto const id : dp[1][n].preorder_traversal) {
        std::cout << id << ' ';
    }
    std::cout << '\n';
}