题目

题目描述

设一个 $n$ 个节点的二叉树$\text{tree}$ 的中序遍历为$(1,2,3,\dots ,n)$，其中数字 $1,2,3,\dots ,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，$\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分$\times \text{subtree}$ 的右子树的加分 $+\text{subtree}$的根的分数。

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

试求一棵符合中序遍历为 $(1,2,3,\dots ,n)$ 且加分最高的二叉树 $\text{tree}$。要求输出

$\text{tree}$ 的最高加分。

$\text{tree}$ 的前序遍历。

输入格式

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

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

输出格式

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

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

输入输出样例

输入

5 5 7 1 2 10

输出

145 3 1 2 4 5

说明/提示

$n<30$。

分数$<100$。

题解

1.

因为中序遍历为$(1,2,3,\dots ,n)$，所以我们可以得到每一棵子树都满足：左子树各节点序号<根<右子树各节点序号 所以想到区间DP

2.DP

1.状态

我们设$dp[i][j]$表示从$i$ ~ $j$生成树的最大加分

2.阶段

len呗，区间DP基本操作

3.转移

枚举根节点$k(l<k<r)$，$dp[l][r]=min(dp[l][r],dp[l][k-1]\ast dp[k+1][r]+a[k])$

for(int len=1;len<n;++len){ for(int l=1;l+len<=n;l++){ int r=l+len; dp[l][r]=dp[l+1][r]+a[l]; root[l][r]=l; for(int k=l+1;k<r;++k){ if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+a[k]){ dp[l][r]=dp[l][k-1]*dp[k+1][r]+a[k]; root[l][r]=k; } } } }

4.输出路径

每次转移的时候保存一下根节点，有了根节点不就好做了吗\ (^o^)/~

void print(int l,int r){ if(l>r){ return; } printf("%d ",root[l][r]); if(l==r){ return; } print(l,root[l][r]-1); print(root[l][r]+1,r); }

5.代码

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=35; int n; int dp[MAXN][MAXN]; int a[MAXN]; int root[MAXN][MAXN]; void print(int l,int r){ if(l>r){ return; } printf("%d ",root[l][r]); if(l==r){ return; } print(l,root[l][r]-1); print(root[l][r]+1,r); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ dp[i][i]=a[i]; dp[i][i-1]=1; root[i][i]=i; } for(int len=1;len<n;++len){ for(int l=1;l+len<=n;l++){ int r=l+len; dp[l][r]=dp[l+1][r]+a[l]; root[l][r]=l; for(int k=l+1;k<r;++k){ if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+a[k]){ dp[l][r]=dp[l][k-1]*dp[k+1][r]+a[k]; root[l][r]=k; } } } } printf("%d\n",dp[1][n]); print(1,n); return 0; }