加分二叉树

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1183 字

中序遍历固定为1..n，每点有分数，子树加分

一本通
练习

正文

/*
原题：加分二叉树（一本通 5.2 练习1）
题意：中序遍历固定为 1..n，每点有分数，子树加分 = 左加分*右加分 + 根分数（空子树记 1）。求最高总分及前序遍历。
思路：区间 DP。f[i][j] 为区间 [i,j] 的最高分，枚举根 k 递归合并，记 root[i][j]=k 用于重建前序。
复杂度：O(n^3) 时间，O(n^2) 空间。
易错点：空子树记 1；结果可能超 int，用 long long；前序按 root 递归输出。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=35;
long long dp[N][N];
int root[N][N];
int a[N];
void out(int l,int r){
    if(l>r)return;
    int k=root[l][r];
    cout<<k<<" ";
    out(l,k-1);
    out(k+1,r);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i][i]=a[i];
        root[i][i]=i;
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            dp[i][j]=-1;
            for(int k=i;k<=j;k++){
                long long left=(k==i)?1:dp[i][k-1];
                long long right=(k==j)?1:dp[k+1][j];
                long long val=left*right+a[k];
                if(val>dp[i][j]){
                    dp[i][j]=val;
                    root[i][j]=k;
                }
            }
        }
    }
    cout<<dp[1][n]<<"\n";
    out(1,n);
    cout<<"\n";
    return 0;
}

加分二叉树

正文

一本通·提高篇的其它内容