题意
Time Limit: 5000MS | Memory Limit: 30000K | |
Total Submissions: 4397 | Accepted: 1278 |
Description
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile.
You are to write a program to determine the minimum of the total score.
Input
The last test case is followed by one zero.
Output
Sample Input
1 100 3 3 4 3 4 1 1 1 1 0
Sample Output
0 17 8
Source
分析
参照fanhqme的题解,此题解毫无用处。
石子合并(每次合并相邻的两堆石子,代价为这两堆石子的重量和,把一排石子合并为一堆,求最小代价)
是一个经典的问题。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了。
呵呵。
呵呵。
代码
#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
co int N=5e4+1;
int n,a[N],t,p,ans;
void work(int x){
int k=a[x]+a[x-1];
ans+=k;
for(int i=x;i<t-1;++i) a[i]=a[i+1];
--t;
for(p=x-1;p&&a[p-1]<k;--p) a[p]=a[p-1];
a[p]=k;
while(p>=2&&a[p]>=a[p-2]){
int d=t-p;
work(p-1);
p=t-d;
}
}
void An_old_Stone_Game(){
for(int i=0;i<n;++i) read(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]) work(t-2);
}
while(t>1) work(t-1);
printf("%d\n",ans);
}
int main(){
while(read(n)) An_old_Stone_Game();
return 0;
}