P1040 [NOIP2003 提高组] 加分二叉树
题目描述
设一个 个节点的二叉树 的中序遍历为,其中数字 为节点编号。每个节点都有一个分数(均为正整数),记第 个节点的分数为 , 及它的每个子树都有一个加分,任一棵子树 (也包含 本身)的加分计算方法如下:
的左子树的加分 的右子树的加分 的根的分数。
若某个子树为空,规定其加分为 ,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为 且加分最高的二叉树 。要求输出
- 的最高加分。
- 的前序遍历。
对于全部的测试点,保证 ,节点的分数是小于 的正整数,答案不超过 。
解法
因为中序遍历保证是 ,所以可以从这里入手。中序遍历中,如果一个数是这颗子树的根,那么中序遍历的序列以这个数为分割点的左边是左子树,右边是右子树。
我们考虑区间 ,设计状态 表示中序遍历中 区间的组成的子树所可能得到分数的最大值。
则有状态转移方程:
那么第一问就做完了。
我们可以在转移的时候加一个判断,用 表示 中取得最大值是这个区间的根的编号。
用代码表示就是:
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];
rt[i][j] = k;
}
题目要求输出前序遍历,则递归输出即可。
code:
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN = 35;
int n;
int val[MAXN];
int dp[MAXN][MAXN];
int rt[MAXN][MAXN];
void print(int l,int r){
if(l > r) return;
cout << rt[l][r] << " ";
print(l,rt[l][r] - 1);
print(rt[l][r] + 1,r);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 0;i <= MAXN - 1;i++){
for(int j = 0;j <= MAXN - 1;j++){
dp[i][j] = 1;
}
}
for(int i = 1;i <= n;i++) cin >> val[i],dp[i][i] = val[i];
for(int i = 1;i <= n;i++) rt[i][i] = i;+
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];
rt[i][j] = k;
}
}
}
}
cout << dp[1][n] << endl;
print(1,n);
return 0;
}