博客

关于四边形不等式或石子合并的资料。网上有很多。但有不少都是语焉不详,直接抛给你几个结论,让人很难理解。这篇文章将以石子合并为例。证明关于四边形不等式的一些结论。算是一个温习。

【题面】

在一个操场上摆放着一排n（n≤20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。

【算法分析】

下面只讨论最小得分的情况，最大得分的情况类似。

设

f[I,j]=min{f[I,k]+f[k+1,j]+w[I,j]}{i<=k<j}，特别的，f[I,i]=0。

很明显,这是一个O(n^3)的动规

【算法优化】

下面是重头戏。

首先给出两个定义：

(1)当函数w[i,j]满足w[i,j]+w[i’,j’]<=w[i’,j]+w[i,j’],i<=i'<=j<=j’时，称w满足四边形不等式。

(2)当函