「SDOI2008」石子合并 - GarsiaWachs

题目大意

    在一个操场上摆放着一排$N$堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的$2$堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
    试设计一个算法，计算出将$N$堆石子合并成一堆的最小得分。

题目分析

这道题显然不能再用四边形不等式了，可以使用神奇的GarsiaWachs算法。
算法步骤如下：

• 找到一个位置$k$，满足$a_{k-1}\le a_k$，合并$k-1$与$k$。
• 从$k$开始向左找第一个$a_j\gt a_{k-1}+a_k$的$j$，把合并后的值插到$j$的后面。
• 重复执行以上步骤直到只剩一个元素。

为什么是对的我也不知道。
时间复杂度上界是$O(n^2)$，实际时间往往跑得很快，除非特殊构造数据。
可以使用平衡树优化合并过程将复杂度降为$O(n\log n)$。

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005;

int n,cnt;
LL ans=0,a[maxn];

void Combine(int k) {
	LL tmp=a[k-1]+a[k];
	ans+=tmp;
	for(int i=k; i<=cnt; i++)a[i]=a[i+1];
	cnt--;
	int j=1;
	for(j=k-1; j>1&&a[j-1]<tmp; j--)a[j]=a[j-1];
	a[j]=tmp;
	while(j>=3&&a[j]>=a[j-2]) {
		int delta=cnt-j;
		Combine(j-1);
		j=cnt-delta;
	}
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	cnt=1;
	for(int i=2; i<=n; i++) {
		a[++cnt]=a[i];
		while(cnt>=3&&a[cnt-2]<=a[cnt])Combine(cnt-1);
	}
	while(cnt>=2)Combine(cnt);
	printf("%lld\n",ans);
	return 0;
}