RQNOJ

P49 加分二叉树 题解

题目中说二叉树的中序遍历是顺序的,这说明:对于区间[i,j]其根root满足i<=root<=j

也就是说,对于区间[i,j]其最大加分为选取其中一个作为根R,其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R],对于所有可能的R取表达式最大值.状态转移方程:

\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意:题目要求若一棵树没有左或者右子树,则其加分为存在的那棵子树

初始值for i=1 to n f[i][i]=v[i];

输出便利的方法是:每次记录取到最大值时的根节点编号,设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
Continue reading

P156 吞噬比赛 NlogN最长不下降子序列

MY CODE:

Continue reading