题目大概都是这样的：

  设有N堆沙子排成一排，其编号为1，2，3，…，N（N<=300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为 1  3  5  2 我们可以先合并1、2堆，代价为4，得到4 5 2 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

dp的方程很显然：

区间DP dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j])   i<=k<=j 复杂度 N^3

这同时也是一个四边形优化DP的标准形式，对于i到j段的最优值s[i][j]满足：  s[i][j-1]<=s[i][j]<=s[i+1][j]

可以减小枚举范围，复杂度N^2

TYVJ 1055:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1100;
const int INF=0x3f3f3f3f;

int n,a[maxn];
int sum[maxn];
int dp[maxn][maxn],s[maxn][maxn];

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
            s[i][i]=i;
        }
        for(int len=2;len<=n;len++)
        {
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                dp[i][j]=INF;
                for(int k=s[i][j-1];k<=s[i+1][j]&&k<j;k++)
                {
                    int temp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                    if(temp<dp[i][j])
                    {
                        dp[i][j]=temp;
                        s[i][j]=k;
                    }
                }
            }
        }
        printf("%d\n",dp[1][n]);
    }
    return 0;
}

如果n非常大，时间和空间都不满足。

可以用GarsiaWachs算法：

http://fanhq666.blog.163.com/blog/static/81943426201062865551410/

石子合并（每次合并相邻的两堆石子，代价为这两堆石子的重量和，把一排石子合并为一堆，求最小代价）
是一个经典的问题。dp可以做到O(n*n)的时间复杂度，方法是：
设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算法可以把时间复杂度压缩到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)

事情并没有结束。
我在poj1738上看到了一个50000个数的石子合并，很痛苦地想：要写平衡树了:(
但是当我把朴素实现的代码
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/1738.cpp
交上去的时候，发现，AC了？！

为什么？
平方的复杂度，50000的数据......
我着手分析。
首先，每次combine()（见源代码）操作的时候，并不一定都会访问到整个数组。
从随机的角度来讲，新合并出来的石子堆相比那些已经合并许许多多次的石子堆来说，
并不是很“牛”。因为他并不很牛，所以j的值也不比k小得了多少。
并且我们维护的“2-递减”序列本身就有一个很强的序的关系，所以从某种感觉上讲，combine()递归调用的次数很少。

这只是一个感性的想法，实际上，它唯一能够提供给我们的想法是：隐藏在O(n*n)里的常数非常小！
有多小？自己测试一下，（我的笔记本比较慢）大约实际时间＝0.00000036*n*n毫秒
但即使这样，按照多组数据的时间换算一下，还是应该超时的呀。
看题目最后一句话：
For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.
这句话等价于：每个数都不会很大（要合并49999次呢！），继续等价于：有好多数是相同的。

即使这样，又有什么不同呢？
当然了！
我绘制了一幅平均每次k-j的值关于n的图像
 其中橘红色的列是我生成的随机的实数作为数据测的结果，而蓝色的是随机生成的［1，1024］间的整数测得的结果。
很明显，小范围的数据大大“加速”了算法，甚至可能引起复杂度上的差异。

就是这样，让本该写一个平衡树的题用数组AC了。
呵呵。
呵呵。

poj 1738 

bzoj 3229

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=55000;

int a[maxn];
int n,t,ans;

void combin(int k)
{
    int temp=a[k]+a[k-1];
    ans+=temp;
    for(int i=k;i+1<t;i++)
    {
        a[i]=a[i+1];
    }
    t--;
    int j=k-1;
    for(;j>0&&a[j-1]<temp;j--)
    {
        a[j]=a[j-1];
    }
    a[j]=temp;
    while(j>2&&a[j-2]<=a[j])
    {
        int d=t-j;
        combin(j-1);
        j=t-d;
    }
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
    for(int i=0;i<n;i++)
        scanf("%d",a+i);
    t=1,ans=0;
    for(int i=1;i<n;i++)
    {
        a[t++]=a[i];
        while(t>=3&&a[t-3]<=a[t-1])
            combin(t-2);
    }
    while(t>1) combin(t-1);
    printf("%d\n",ans);
}
    return 0;
}
/*
5
186 64 35 32 103
*/

石子合并的动态规划问题