「NOIp2003」 加分二叉树 - 区间DP

题目链接:传送门

Description

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

Input

第1行:一个整数n(n<30),为节点个数。 第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

Output

第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。 第2行:n个用空格隔开的整数,为该树的前序遍历。

Solution

因为题目给出了中序遍历,且一棵子树在中序遍历中一定是一段连续的区间,因此对子树的计算便可转化为对区间的计算。

因此这道题就可以转化为区间DP

我们设F[i][j]F[i][j]表示在区间[i,j]中的最大加分,也就是从i到j组成的子树的最大加分,

那么便有区间DP的套路: F[i][j]=max(F[i][j],F[i][k1]F[k+1][j]+F[k][k])F[i][j]=\max(F[i][j],F[i][k-1] * F[k+1][j]+F[k][k])

当然当k==i || k==j时我们要特殊处理下

至于输出前序遍历的话,我们可以开一个root[][]数组表示i到j的根,输出时递归处理即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
int n;
int a[35],f[50][50],root[50][50];
inline void print(int l,int r){
if(l==r){
printf("%d ",l);
return ;
}
if(r-l==1){
if(root[l][r]==l)printf("%d %d ",l,r);
else printf("%d ",r,l);
return ;
}
printf("%d ",root[l][r]);
print(l,root[l][r]-1);
print(root[l][r]+1,r);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i][i]=a[i];
for(int l=1;l<n;l++)
for(int i=1;i<=n-l;i++){
int j=i+l;
for(int k=i;k<=j;k++){
int a1=f[i+1][j]+f[i][i],a2=f[i][j-1]+f[j][j],a3=f[i][k-1]*f[k+1][j]+f[k][k];
if(k==i && a1>f[i][j])
f[i][j]=a1,root[i][j]=i;
else if(k==j && a2>f[i][j])
f[i][j]=a2,root[i][j]=j;
else if(a3>f[i][j])
f[i][j]=a3,root[i][j]=k;
}
//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
cout<<f[1][n]<<endl;
print(1,n);
return 0;
}
感谢你的赞赏!