Via FHQ神犇http://fanhq666.blog.163.com/blog/static/81943426201062865551410/
石子合并（每次合并相邻的两堆石子，代价为这两堆石子的重量和，把一排石子合并为一堆，求最小代价）是一个经典的问题。dp可以做到O(n*n)的时间复杂度，方法是：
朴素DP做法
设f[i,j]为合并从i到j的石子所用最小代价。
f[i,j]=min(sum(i,j)+f[i,k]+f[k+1,j])对所有i<=k<j，其中sum(i,j)表示从i到j的石子重量之和。
设上式取等时k的值为w[i,j]，有神牛证明过：w[i,j]>=w[i,j-1],w[i,j]<=w[i+1,j]
这样，枚举k的时候，就有了一个上下界，从而搞掉了一维。
GarsiaWachs算法
而GarsiaWachs算法可以把时间复杂度压缩到O(nlogn)。
具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W,Lemma X,Lemma Y,Lemma Z。
只能说一个概要吧：
设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，（方便起见设A[-1]和A[n]等于正无穷大）
那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。
有定理保证，如此操作后问题的答案不会改变。
举个例子：
186 64 35 32 103
因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面
186 64（k=3,A[3]与A[2]都被删除了） 103
186 67（遇到了从右向左第一个比67大的数，我们把67插入到他后面） 64 103
186 67 64 103 （有定理保证这个序列的答案加上67就等于原序列的答案）
现在由5个数变为4个数了，继续！
186 （k=2,67和64被删除了）103
186 131（就插入在这里） 103
186 131 103
现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）
234 186
420
最后的答案呢？就是各次合并的重量之和呗。420+234+131+67=852，哈哈，算对了。
证明嘛，基本思想是通过树的最优性得到一个节点间深度的约束，之后 证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的 深度不会改变。详见TAOCP。
实现
具体实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”
朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化（好熟悉的优化方法），使得最终复杂度为O(nlogn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <cstdio> #define NMax 50000 using namespace std; int A[NMax],N,T; int ret; void combine(int k){ int tmp=A[k]+A[k-1],j; ret+=tmp; for (int i=k;i<T-1;i++)A[i]=A[i+1]; T--; for (j=k-1;j>0 && A[j-1]<tmp;j--)A[j]=A[j-1]; A[j]=tmp; while (j>=2 && A[j]>=A[j-2]){ int d=T-j; combine(j-1); j=T-d; } } int main() { while (scanf("%d",&N),N){ for (int i=0;i<N;i++)scanf("%d",A+i); T=1;ret=0; for (int i=1;i<N;i++){ A[T++]=A[i]; while (T>=3 && A[T-3]<=A[T-1])combine(T-2); } while (T>1)combine(T-1); printf("%d\n",ret); } return 0; } |
[Dr.Lib]Note:Algorithms – GarsiaWachs by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.