更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527051

大意

石子合并，$n = 1000$，求最小值。

思路

首先 $\mathcal{O}(n ^ 3)$ 的复杂度肯定是不可以的。

我们考虑优化，不难发现，对于 $w(i, j)$ 满足：

$$w(i, j - 1) + w(i + 1, j) \le w(i, j) + w(i - 1,j - 1)$$

所以这个 $w$ 满足四边形不等式，故 $f$ 也满足。

然后我们定义这个 $G(k) = f(i, k) + f(k + 1, j)$，所以 $G(k)$ 为凹函数，则最小值在一个区间内取得，我们可以记录 $[i, j]$ 区间的决策点，这样你在算第 $[i, j]$ 的时候，区间 DP 的点 $k$ 就可以在 $s[i][j - 1]$ 和 $s[i + 1][j]$ 之间取得。