石子合并sdoi2008

2024-02-20 16:18

文章标签 合并 sdoi2008 石子

本文主要是介绍石子合并sdoi2008，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述 Description
　　在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

　　试设计一个算法，计算出将N堆石子合并成一堆的最小得分。
输出描述 Output Description
　　共一个数，即N堆石子合并成一堆的最小得分。
样例输入 Sample Input
4

1
1
样例输出 Sample Output

8
数据范围及提示 Data Size & Hint
对于 30% 的数据，1≤N≤100
对于 60% 的数据，1≤N≤1000
对于 100% 的数据，1≤N≤40000
对于 100% 的数据，1≤A≤200
思路：这个题非常经典，但省选也是够了，范围变得超大，先写了一个朴素的，过了三个点，又写了一个四边形优化，只多过了2个点，后来才知道这个题有专门的做法—- GarsiaWachs；
设一个序列是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 67 64 103 （有定理保证这个序列的答案加上67就等于原序列的答案）
现在由5个数变为4个数了，继续！
变成了:
186 131 103
现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）
234 186
420
最后的答案呢？就是各次合并的重量之和呗。420+234+131+67=852，
具体证明比较复杂，基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变。详见TAOCP。
这个题最好用平衡树维护一下，复杂度为（nlogn）当然朴素也能过为（n*n）；

#include <iostream>  #include <cstring>  #include <cstdio>  using namespace std;  const int N = 50005;  int stone[N];  int n,t,ans;  void combine(int k)  {  int tmp = stone[k] + stone[k-1];  ans += tmp;  for(int i=k;i<t-1;i++)  stone[i] = stone[i+1];  t--;  int j = 0;  for(j=k-1;j>0 && stone[j-1] < tmp;j--)  stone[j] = stone[j-1];  stone[j] = tmp;  while(j >= 2 && stone[j] >= stone[j-2])  {  int d = t - j;  combine(j-1);  j = t - d;  }  }  int main()  {  cin>>n;    for(int i=0;i<n;i++)  scanf("%d",stone+i);  t = 1;  ans = 0;  for(int i=1;i<n;i++)  {  stone[t++] = stone[i];  while(t >= 3 && stone[t-3] <= stone[t-1])  combine(t-2);  }  while(t > 1) combine(t-1);  printf("%d\n",ans); return 0;  }