题解

核心算法

dp[l][r] 为区间合成一堆的最小代价，枚举最后一次分割点。

思路推导

最后一次必把两个相邻子区间合并，代价再加区间总和。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(n^3)
• 空间复杂度：O(n^2)

易错点

按区间长度递增；区间和用前缀和。

完整标程见 std/main.cpp。