加分二叉树|P1040

https://www.luogu.com.cn/problem/P1040

题目描述

设一个 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 的前序遍历。

输入格式

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

第 2 行 n 个用空格隔开的整数，为每个节点的分数

输出格式

第 1 行 1 个整数，为最高加分（Ans≤4,000,000,000）。

第 2 行 n 个用空格隔开的整数，为该树的前序遍历。

输入输出样例

输入 #1

5
5 7 1 2 10

输出 #1

145
3 1 2 4 5

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n\<30，节点的分数是小于 100 的正整数，答案不超过 4000000000。

裸区间DP诶。。。

考虑区间转移：

subtree的分数 = subtree 的左子树的加分 × subtree 的右子树的加分 + subtree 的根的分数。

题都给你了，用就得了。

每个区间都可以通过枚举根节点求出来

蚌

直接看代码！

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[40];
int dp[40][40];//写个区间DP
void init(){//初始化。
    for(int i=0;i<40;i++){
        for(int j=0;j<40;j++){
            dp[i][j]=1;
        }
    }
}
int root[40][40];
void dfs(int l,int r){//根据记录每个区间的根递归就得了
    if(l==r){
        cout<<l<<' ';
        return;
    }
    cout<<root[l][r]<<' ';
    if(l<=root[l][r]-1)dfs(l,root[l][r]-1);
    if(root[l][r]-1<=r)dfs(root[l][r]+1,r);
}
signed main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i][i]=a[i];
    }
    for(int len=2;len<=n;len++){//最外层枚举区间长度
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){//扫根
                if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k]){
                    dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
                    root[i][j]=k;//得记一下根的位置
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;//输出
    dfs(1,n);
    return 0;
}