洛谷P1040 加分二叉树(树形dp)

加分二叉树

时间限制: 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的前序遍历

 

输入

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

输出

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

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5

提示

 

来源

提高组-2003年NOIP

题目类型:

树形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 ;
}
上一篇:temp8


下一篇:Python编程Day7——字符编码、字符与字节、文件操作