1090 加分二叉树
2003年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题解
查看运行结果
题目描述 Description
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空
子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入描述 Input Description
第1行：一个整数n（n<=30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数<=100）
输出描述 Output Description
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
样例输入 Sample Input
5
5 7 1 2 10
样例输出 Sample Output
145
3 1 2 4 5
数据范围及提示 Data Size & Hint
n（n<=30)
分数<=100
这道题就是简单的区间dp，看到加分=subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数就应该立即想到，所以我们只需要不断的扩大区间求最优就行。状态转移方程如下：
dp[i][j] = max(dp[i][j], dp[i][k - 1] * dp[k + 1][j] + dp[k][k]);
至于先序序列，我们只需要记号每个最优区间的根节点就好，看代码就明白了，代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int dp[105][105];
int root[105][105];
int a[105];
void Find(int l, int r)
{
int k = root[l][r];
cout << k << ' ';
if(k > l) {
Find(l, k - 1);
}
if(k < r) {
Find(k + 1, r);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
root[i][i] = i;
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
if(i == j && i) {
dp[i][j] = a[i];
}
else
dp[i][j] = 1;
}
}
for(int len = 2; len <= n; len++) {
for(int i = 1; i <= n - len + 1; 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] + dp[k][k]) {
dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + dp[k][k];
root[i][j] = k;
}
}
}
}
cout << dp[1][n] << endl;
Find(1, n);
return 0;
}