年轻人的第一道绿题
感谢半场历史考试
在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次 只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。
$1\leq N\leq 100$，$0\leq a_i\leq 20$。
我们在此只考虑最大得分
要注意的是, 石子首尾相连成环
出现环的问题, 我们在解决时必然从某一个节点入手, 此时相当于将环从该节点处断开, 即将环问题转换成了链问题
然而对于一个 $ n $ 元环(化学乱入), 我们能够选择 $ n $ 种不同的断开方式, 如果 将每一种方式生成的子问题都加以考虑就过于复杂, 此时可以通过将问题空间扩大两倍, 将环展开成链后复制一部分, 首尾相接附加在原链后, 然后对所有长度为 $ n $ 的区间 求值即可
作为一道动态规划题, 仍然从暴力的角度入手
定义 $ merge(l,r) $ 为合并 $ [l,r] $ 能够产生的最大收益, 对于平凡情况 $ l = r $
$$ merge(l,l) = 0 $$
对于非平凡情况, 我们能够作出的选择是在哪个位置进行合并. 此时只需要 递归求解合并该点左侧, 右侧的所有石子分别能产生的最大收益, 再将这个值与 合并 $ [l,r] $ 石堆后产生的石堆的石子数字相加.
递归方程式为
$$
merge(l,r) = \begin{cases}
0 & l = r \\
max \{ merge(l,p) + merge(p + 1,r) \vert l \leq p \leq r \} +
\sum _ {k = l} ^ r stoneNum[k] & l \neq r
\end{cases}
$$
首先, 类似 DFS 的暴力解一定是会超时的, 基于动态规划的特性我们为其提供记忆话 的代码
石子的总数可以通过预先计算区间和以计算, 在我的 GitHub 代码中, 可以通过前缀和 以减少时间复杂度