加分二叉树

我们可以枚举中间这个 k 的位置，然后分别递归计算左右子树，这就让我们想到这是一个和区间有关的，我们可以用区间dp来解决。

\(f[i][j]\) 表示 i， j 这个区间的最大分值。用一个很板子的区间dp就可以解决了。

至于求前序遍历，我们也只需要通过递归然后枚举中间的根，第一个满足最大值的就是字典序最小的，这样就可以解决了。

能量项链

破环成链，然后很明显能看出来这是一个区间dp，直接套板子。（貌似需要开long long）

矩阵取数游戏

由于每一层之间都是相互独立的，所以我们可以对于每一行进行区间dp，然后存一个 res 去累加每一行的分值。

对于每一次的 \(2 ^ i\) 我们可以采用快速幂来解决。