首页 > 代码库 > NOIP2003TG 加分二叉树 区间DP
NOIP2003TG 加分二叉树 区间DP
加分二叉树 （binary）
【问题描述】
设一个 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
思路
{
因为是中序遍历，所以如果i为根节点，那么1..i-1是左子树，i+1..j为右子树
于是你就发现了每次的决策
所以这是一道区间DP。。。
用f[i,j]为i..j构成的树所能得到的最大分值
那么可以得到DP方程：
f[i,j]:=fen[i] | i=j
f[i,j]:=max(f[i,j],f[i,k-1]*f[k+1,j]+fen[k]) | i<=k<=j
//注意子树相乘时如果子树为0就当1 处理,
//if f[i,k-1]=0 then f[i,k-1]:=1;
//if f[k+1,j]=0 then f[k+1,j]:=1;
//例如：
// 如果左子树为0 ， 那么左子树当为1 ，因为1*右子树=右子树
}
代码
1 program no; 2 const 3 inf=‘binary.in‘; 4 outf=‘binary.out‘; 5 var 6 i,j,k,n,t1,t2:longint; 7 f,root:array[0..100,0..100] of int64; 8 fen:array[0..100] of longint; 9 10 procedure outfirst(s,e:longint);11 begin12 if s>e then exit;13 write(root[s,e],‘ ‘);14 outfirst(s,root[s,e]-1);15 outfirst(root[s,e]+1,e);16 end;17 18 begin19 assign(input,inf);20 assign(output,outf);21 reset(input);22 rewrite(output);23 24 readln(n);25 for i:= 1 to n do26 begin27 read(fen[i]);28 f[i,i]:=fen[i];29 root[i,i]:=i;30 end;31 32 for i:=n downto 1 do33 for j:= i+1 to n do34 for k:= i to j do35 begin36 if f[i,k-1]=0 then f[i,k-1]:=1;37 if f[k+1,j]=0 then f[k+1,j]:=1;38 t1:=f[i,k-1];39 t2:=f[k+1,j];40 if f[i,j]<t1*t2+fen[k] then41 begin42 f[i,j]:=t1*t2+fen[k];43 root[i,j]:=k;44 end;45 end;46 47 writeln(f[1,n]);48 outfirst(1,n);49 50 close(input);51 close(output);52 end.
NOIP2003TG 加分二叉树 区间DP