Description
在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将N堆石子合并成一堆的最小得分。
Input
第一行是一个数N。
以下N行每行一个数A，表示石子数目。
Output
共一个数，即N堆石子合并成一堆的最小得分。
Sample Input
4
1
1
1
1
Sample Output
8
HINT
对于 100% 的数据，1≤N≤40000
对于 100% 的数据，1≤A≤200
分析：
我第一眼以为就是一个简单的dp
还在怀疑十年前的sdoi竟然这么简单
然而，当我看到了n<=40000
朴素的n^3肯定是不行了
看这个数据范围，起码要nlogn
此题如果数据范围是100，就是一道基础的动态规划题
但是数据范围到了40000，就是一道比较难的题了
这里引入GarsiaWachs算法
主要过程是这样的：
从左往右找，找到第一个k，使得a[k-1]<=a[k+1]，我们把这两堆石子合并，把代价加在sum上
然后从k往左找，找到第一个j，使得a[j]>合并后的石头，把合并后的石头放在a[j]后
合并n-1次后，sum就是合并n堆石子的最小代价
之下是网上不错的讲解：
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。
解题思路:
（这是从网上扒下来的一个关于GarsiaWachs算法的解释）
这类题目一开始想到是DP, 设dp[i][j]表示第i堆石子到第j堆石子合并最小得分.
状态方程: dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
sum[i]表示第1到第i堆石子总和. 递归记忆化搜索即可.不过此题有些不一样, 1<=n<=40000范围特大
问题分析:
(1). 假设我们只对3堆石子a,b,c进行比较, 先合并哪2堆, 使得得分最小.
score1 = (a+b) + ( (a+b)+c )
score2 = (b+c) + ( (b+c)+a )
再次加上score1 <= score2, 化简得: a <= c, 可以得出只要a和c的关系确定,
合并的顺序也确定.
(2). GarsiaWachs算法, 就是基于(1)的结论实现.找出序列中满足stone[i-1] <=
stone[i+1]最小的i, 合并temp = stone[i]+stone[i-1], 接着往前面找是否
有满足stone[j] > temp, 把temp值插入stone[j]的后面(数组的右边). 循环
这个过程一直到只剩下一堆石子结束.
(3). 为什么要将temp插入stone[j]的后面, 可以理解为(1)的情况
从stone[j+1]到stone[i-2]看成一个整体 stone[mid],
现在stone[j],stone[mid], temp(stone[i-1]+stone[i-1]),
因为temp < stone[j],
因此不管怎样都是stone[mid]和temp先合并, 所以讲temp值插入stone[j]的后面是不影响结果.
tip
我在这里用的模拟链表，链接的时候一定要注意
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=0x33333333;
const int N=50000;
int t[N][2],a[N],ans=0;
int n;
void doit()
{
int i,j,k;
for (i=1;i<n;i++)
{
j=t[0][1];
int fro=t[j][0],beh=t[j][1];
while (a[fro]>a[beh])
{
j=beh;
fro=t[j][0];
beh=t[j][1];
}
int tt=a[j]+a[fro];
ans+=tt;
a[j]=tt;
t[t[fro][0]][1]=t[j][1]; t[t[j][1]][0]=t[fro][0]; //del
k=t[fro][0];
while (a[k]<=tt)
k=t[k][0];
t[j][1]=t[k][1]; t[t[k][1]][0]=j; //insert
t[j][0]=k; t[k][1]=j;
}
printf("%d",ans);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),t[i][0]=i-1,t[i][1]=i+1;
a[0]=INF; a[n+1]=INF;
t[0][1]=1; t[n+1][0]=n;
doit();
return 0;
}