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
Source
传送门
原版的石子合并，N却有整整40000……
基本的DP是O(N^3)的，
平行四边形优化过后是O(N^2)的，但是仍然不能满足这题的条件。
这里要用到GarsiaWachs算法。
步骤：
1.找到第一个a[u-1]<=a[u+1]的位置；
2.将a[u-1]和a[u]合并（加起来）；
3.把合并后的结果插入到位置v，使得a[v]>=a[u]。
如此重复上述步骤，合并n-1次，得到的就是最优结果……
其实我不太知道原理……
证明还是网上百度吧。。。
时间复杂度O(N^2)……这是最坏情况下的，，听说平均是O(N log N)
反正加上平衡树就是稳定O(N log N)了，，（我没加）
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int
N=40005,
MAX=9000000;
int n,a[N];
int main(){
n=read();
for (int i=1;i<=n;i++) a[i]=read();
a[0]=a[n+1]=MAX;
int m=n,ans=0;
for (int i=1;i<n;i++){
int k;
for (int j=1;j<=m;j++)
if (a[j-1]<=a[j+1]){
k=j; break;
}
a[k-1]+=a[k];
for (int j=k;j<m;j++) a[j]=a[j+1];
ans+=a[--k];
while (k && a[k-1]<=a[k])
swap(a[k-1],a[k]),k--;
a[m--]=MAX;
}
printf("%d\n",ans);
return 0;
}
