题意:给定一圈石子,将相邻的两堆石子合并,花费为合并后的石子数。给定一开始每一堆石子的个数,求合并的最小花费。(石子堆数<=1000)

分析:

由于是一圈石子,所以我们将其倍增以消除环的影响,然后很自然可以得出状态转移方程:设f(i,j)表示从i到j的石子合并的最小花费,sum[i][j]表示从i到j的石子共有多少个(程序中用前缀和)。
$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j])
$$
但是这是O(n3)的算法。所以我们需要优化。
注意到sum[i][j]满足四边形关系,包含单调关系,所以f一定满足四边形不等式。由此,我们再用一个数组s[i][j]表示区间f[i,j]是通过k=s[i][j]使得f[i][j]最小的,那么状态转移方程可以变为:

$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j]) \text{(s[i][j-1]\textless =k\textless =s[i+1][j])}
$$