加分二叉树
时间限制: 1 Sec 内存限制: 125 MB
提交: 11 解决: 7
题目描述
设一个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的前序遍历
输入
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
输出
第2行：n个用空格隔开的整数，为该树的前序遍历。
样例输入
5
5 7 1 2 10
样例输出
145
3 1 2 4 5
提示
来源
题目类型：
树形dp
思路：
首先，我们要做的就是设计状态，其实就是设计dp数组的含义，它要满足无后效性。关注这个 左子树*右子树+根 我只要知道左子树分数和右子树分数和根的分数（已给出），不就可以了吗？管他子树长什么样！
所以，我们f数组存的就是最大分数，怎么存呢？
我们发现：子树是一个或多个节点的集合。
那么我们可不可以开一个f[i][j]，f[i][j]来表示节点i到节点j成树的最大加分呢？可以先保留这个想法（毕竟暂时也想不到更好的了）。
如果这样话，我们就来设计状态转移方程。按照刚刚的设计来说的话，我们的答案就是f[1][n]了，那么我们可以从小的子树开始，也就是len，区间长度。有了区间长度我们就要枚举区间起点，i为区间起点，然后就可以算出区间终点j。通过加分二叉树的式子我们可以知道，二叉树的分取决于谁是根，于是我们就在区间内枚举根k。
特别的，f[i][i]=a[i]f[i][i]=a[i]，其中a[i]为第i个节点的分数。
因为是要求最大值，所以我们就可以设计出f[i][j]=MAX(f[i][k-1]*f[k+1][j]+f[k][k])f[i][j]=MAX(f[i][k−1]*f[k+1][j]+f[k][k])于是乎，我们就自己设计出了一个dp过程，因为是顺着来的，所以很少有不成立的。
至于输出前序遍历，我们再设计一个状态root[i][j]来表示节点i到节点j成树的最大加分所选的根节点。所以我们按照$根->左->右$的顺序递归输出即可。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;
typedef long long ll;
ll n;
//f[i][j]表示i到j子树的最大分数
ll f[MAXN][MAXN],root[MAXN][MAXN];
void print(ll l, ll r) {
if (l > r)return;
cout<<root[l][r]<<" ";//打印根
if (l == r)return;
print(l, root[l][r] - );//打印左子树
print(root[l][r]+,r);//打印右子树
}
int main()
{
cin>>n;
memset(f,,sizeof(f));
for(int i=;i<=n;i++)
{
cin>>f[i][i];
root[i][i]=i;
}
for(int len=;len<n;len++)//以子树的长度遍历，1个节点的子树，2个节点的子树。。。
{
for(int i=;i+len<=n;i++)
{
int j=i+len;
//根从i开始遍历，先假设i到j的子树，i为根
//不考虑它的空子树,所以左子树为空时，左子树为1，而不是0
//f[i][j]=f[i+1][j]+f[i][i];//此时i到j子树的分数
//root[i][j]=i;
//cout<<i<<"到"<<j<<" 最大为:"<<f[i][j]<<" 以"<<i<<"为根"<<endl;
for(int k=i;k<j;k++)//k为根，遍历每一个根，找到能使子树分数最大的根
{ ll zhi = f[i][k-]*f[k+][j]+f[k][k];
//不考虑它的空子树,所以左子树为空时，左子树为1，而不是0
//以右子树为空时，右子树为1，而不是0
if(f[i][k-]==)
{
zhi=f[k+][j]+f[k][k];
}
if(f[k+][j]==)
{
zhi=f[i][k-]+f[k][k];
}
if(f[i][j]<zhi)
{
f[i][j]=zhi;
root[i][j]=k;
//cout<<i<<"到"<<j<<" 最大为:"<<zhi<<" 以"<<k<<"为根"<<endl;
}
}
}
}
cout<<f[][n]<<endl;
print(, n);
return ;
}