P1040 [NOIP2003 提高组] 加分二叉树 分析

· · 个人记录

本题虽然是在树上的操作，但是实际上是区间 DP 的典题。

我们知道：在中序遍历中，一个点左边的序列和右边的序列就是其左子树和右子树。因此，我们的问题就转化为了求区间中的最优分割点 k，使 \sigma_{l,k-1} \times \sigma_{k+1,r} + \sigma_{k,k} 最大。

之后的问题就是找到先序遍历。这实际上也是很简单的。我们将每一个区间的最优分割点保存下来，于是这个点就是这个区间所建的树的根。之后打印即可。

总之，对于中序遍历的问题，我们可以转化为区间上的问题。