转载

石子合并问题（直线版）

首先来个题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=737

有个更难的版本（不过很好玩）：http://www.lydsy.com/JudgeOnline/problem.php?id=3229

题目：

石子合并（一）

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述: 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

输入

有多组测试数据，输入到文件结束。

每组测试数据第一行有一个整数n，表示有n堆石子。

接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开

输出

输出总代价的最小值，占单独的一行

样例输入

3 1 2 3 7 13 7 8 16 21 4 18

样例输出

9 239

最普通的算法O(n^3)：

 1 #include <fstream>  2 #include <iostream>  3 #include <cstdio>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cmath>  7 using namespace std;  8   9 const int N=205; 10 const int INF=0x7fffffff; 11 int n; 12 int a[N],sum[N],dp[N][N]; 13  14 void f(); 15  16 int main(){ 17     //freopen("D://input.in","r",stdin); 18     while(~scanf("%d",&n)){ 19         sum[0]=0; 20         for(int i=1;i<=n;i++){ 21             scanf("%d",&a[i]); 22             sum[i]=sum[i-1]+a[i]; 23         } 24         f(); 25         printf("%d/n",dp[1][n]); 26     } 27     return 0; 28 } 29 void f(){ 30     for(int i=1;i<=n;i++) dp[i][i]=0; 31     for(int r=1;r<n;r++){ 32         for(int i=1;i<n;i++){ 33             int j=i+r; 34             if(j>n) break; 35             dp[i][j]=INF; 36             for(int k=i;k<=j;k++){ 37                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); 38             } 39             dp[i][j]+=sum[j]-sum[i-1]; 40         } 41     } 42 }

224ms

其中，dp[i][j]代表i到j堆的最优值，sum[i]代表第1堆到第i堆的数目总和。有：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])+sum[j]-sum[i-1]。

考虑四边形不等式优化：接近O(n^2)：

 1 #include <fstream>  2 #include <iostream>  3 #include <cstdio>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cmath>  7 using namespace std;  8   9 const int N=205; 10 const int INF=0x7fffffff; 11 int n; 12 int a[N],sum[N],dp[N][N],s[N][N]; 13  14 void f(); 15  16 int main(){ 17     //freopen("D://input.in","r",stdin); 18     while(~scanf("%d",&n)){ 19         sum[0]=0; 20         for(int i=1;i<=n;i++){ 21             scanf("%d",&a[i]); 22             sum[i]=sum[i-1]+a[i]; 23         } 24         f(); 25         printf("%d/n",dp[1][n]); 26     } 27     return 0; 28 } 29 void f(){ 30     for(int i=1;i<=n;i++) dp[i][i]=0,s[i][i]=i; 31     for(int r=1;r<n;r++){ 32         for(int i=1;i<n;i++){ 33             int j=i+r; 34             if(j>n) break; 35             dp[i][j]=INF; 36             for(int k=s[i][j-1];k<=s[i+1][j];k++){ 37                 if(dp[i][j]>dp[i][k]+dp[k+1][j]){ 38                     dp[i][j]=dp[i][k]+dp[k+1][j]; 39                     s[i][j]=k; 40                 } 41             } 42             dp[i][j]+=sum[j]-sum[i-1]; 43         } 44     } 45 }

32ms

优化：原状态转移方程中的k的枚举范围便可以从原来的(i~j-1)变为(s[i,j-1]~s[i+1,j])。

解释下：

四边形不等式优化动态规划原理 :

1.当决策代价函数 w[i][j]满足 w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’)时 ,称 w满足四边形不等式 .当函数 w[i][j]满足 w[i’][j]<=w[i][j’] i<=i’<=j<=j’)时 ,称 w关于区间包含关系单调 .

2.如果状态转移方程 m为石子合并问题（直线版）且决策代价 w满足四边形不等式的单调函数 (可以推导出 m亦为满足四边形不等式的单调函数 ),则可利用四边形不等式推出最优决策 s的单调函数性 ,从而减少每个状态的状态数 ,将算法的时间复杂度由原来的 O(n^3)降低为 O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量 .令 :

s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}

由于决策 s具有单调性 ,因此状态转移方程可修改为 :

石子合并问题（直线版）

证明过程 : ( 转载 )

设 m[i,j] 表示动态规划的状态量。

m[i,j] 有类似如下的状态转移方程：

m[i,j]=opt{m[i,k]+m[k,j]}(i ≤ k ≤ j)

如果对于任意的 a ≤ b ≤ c ≤ d ，有 m[a,c]+m[b,d] ≤ m[a,d]+m[b,c] ，那么 m[i,j] 满足四边形不等式。

以上是适用这种优化方法的必要条件

对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。

通常的动态规划的复杂度是 O(n ³ ) ，我们可以优化到 O(n ² )

设 s[i,j] 为 m[i,j] 的决策量，即 m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]

我们可以证明， s[i,j-1] ≤ s[i,j] ≤ s[i+1,j] （证明过程见下）

那么改变状态转移方程为：

m[i,j]=opt{m[i,k]+m[k,j]} (s[i,j-1] ≤ k ≤ s[i+1,j])

复杂度分析：不难看出，复杂度决定于 s 的值，以求 m[i,i+L] 为例，

(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L] ≤ n

所以总复杂度是 O(n ² )

对 s[i,j-1] ≤ s[i,j] ≤ s[i+1,j] 的证明：

设 m _k [i,j]=m[i,k]+m[k,j] ， s[i,j]=d

对于任意 k<d ，有 m _k [i,j] ≥ m _d [i,j] （这里以 m[i,j]=min{m[i,k]+m[k,j]} 为例 ,max 的类似），接下来只要证明 m _k [i+1,j] ≥ m _d [i+1,j] ，那么只有当 s[i+1,j] ≥ s[i,j] 时才有可能有 m _s[i+1,j] [i+1,j] ≤ m _d [i+1,j]

(m _k [i+1,j]-m _d [i+1,j]) - (m _k [i,j]-m _d [i,j])

=(m _k [i+1,j]+m _d [i,j]) - (m _d [i+1,j]+m _k [i,j])

=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])

=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])

∵ m 满足四边形不等式，∴对于 i<i+1 ≤ k<d 有 m[i+1,k]+m[i,d] ≥ m[i+1,d]+m[i,k]

∴ (m _k [i+1,j]-m _d [i+1,j]) ≥ (m _k [i,j]-m _d [i,j]) ≥ 0

∴ s[i,j] ≤ s[i+1,j] ，同理可证 s[i,j-1] ≤ s[i,j]

证毕

扩展：

以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。

解决这类问题的大概步骤是：

0. 证明 w 满足四边形不等式，这里 w 是 m 的附属量，形如 m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]} ，此时大多要先证明 w 满足条件才能进一步证明 m 满足条件

1. 证明 m 满足四边形不等式

2. 证明 s[i,j-1] ≤ s[i,j] ≤ s[i+1,j]

GarsiaWachs算法优化：

 1 #include <iostream>  2   3 #include <cstring>  4   5 #include <cstdio>  6   7   8   9 using namespace std; 10  11 const int N = 205; 12  13  14  15 int stone[N]; 16  17 int n,t,ans; 18  19  20  21 void combine(int k) 22  23 { 24  25     int tmp = stone[k] + stone[k-1]; 26  27     ans += tmp; 28  29     for(int i=k;i<t-1;i++) 30  31         stone[i] = stone[i+1]; 32  33     t--; 34  35     int j = 0; 36  37     for(j=k-1;j>0 && stone[j-1] < tmp;j--) 38  39         stone[j] = stone[j-1]; 40  41     stone[j] = tmp; 42  43     while(j >= 2 && stone[j] >= stone[j-2]) 44  45     { 46  47         int d = t - j; 48  49         combine(j-1); 50  51         j = t - d; 52  53     } 54  55 } 56  57  58  59 int main() 60  61 { 62  63      while(cin>>n){ 64  65      for(int i=0;i<n;i++) 66  67      scanf("%d",stone+i); 68  69      t = 1; 70  71      ans = 0; 72  73      for(int i=1;i<n;i++) 74  75       { 76  77         stone[t++] = stone[i]; 78  79         while(t >= 3 && stone[t-3] <= stone[t-1]) 80  81          combine(t-2); 82  83       } 84  85      while(t > 1) combine(t-1);  printf("%d/n",ans); 86      } 87  88      return 0; 89  90 } 91

4ms

解释：

对于石子合并问题，有一个最好的算法，那就是GarsiaWachs算法。时间复杂度为O(n^2)。

它的步骤如下：

设序列是stone[]，从左往右，找一个满足stone[k-1] <= stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再从当前位置开始向左找最大的j，使其满足stone[j] > stone[k]+stone[k-1]，插到j的后面就行。一直重复，直到只剩下一堆石子就可以了。在这个过程中，可以假设stone[-1]和stone[n]是正无穷的。

举个例子：

186 64 35 32 103

因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面，得到：186 67 64 103,现在由5个数变为4个数了，继续：186 131 103，现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）234 186，最后得到420。最后的答案呢？就是各次合并的重量之和，即420+234+131+67=852。

基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变。具体实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化，使得最终复杂度为O(nlogn)。

GarsiaWachs算法优化+小细节优化：

 1 #include <fstream>  2 #include <iostream>  3 #include <cstdio>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cmath>  7 using namespace std;  8   9 const int N = 205; 10 const int INF = 0x7fffffff; 11  12 int stone[N]; 13 int n,t,ans; 14  15 void combine(int k) 16 { 17     int tmp = stone[k] + stone[k-1]; 18     ans += tmp; 19     for(int i=k;i<t-1;i++) 20         stone[i] = stone[i+1]; 21     t--; 22     int j = 0; 23     for(j=k-1;stone[j-1] < tmp;j--) 24         stone[j] = stone[j-1]; 25     stone[j] = tmp; 26     while(j >= 2 && stone[j] >= stone[j-2]) 27     { 28         int d = t - j; 29         combine(j-1); 30         j = t - d; 31     } 32 } 33  34 int main() 35 { 36     //freopen("D://input.in","r",stdin); 37     while(~scanf("%d",&n)) 38     { 39         for(int i=1;i<=n;i++) 40             scanf("%d",stone+i); 41         stone[0]=INF; 42         stone[n+1]=INF-1; 43         t = 3; 44         ans = 0; 45         for(int i=3;i<=n+1;i++) 46         { 47             stone[t++] = stone[i]; 48             while(stone[t-3] <= stone[t-1]) 49                 combine(t-2); 50         } 51         while(t > 3) combine(t-1); 52         printf("%d/n",ans); 53     } 54     return 0; 55 }