2298 石子合并

2008年省队选拔赛山东

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

　　试设计一个算法，计算出将N堆石子合并成一堆的最小得分。

输入描述 Input Description

　　第一行是一个数N。

　　以下N行每行一个数A，表示石子数目。

输出描述 Output Description

　　共一个数，即N堆石子合并成一堆的最小得分。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于 30% 的数据，1≤N≤100

对于 60% 的数据，1≤N≤1000

对于 100% 的数据，1≤N≤40000

对于 100% 的数据，1≤A≤200

思路：原来是想用区间dp，但数据太大。就这样了。。。

(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]

的后面是不影响结果.

 1 #include<cstdio>
 2 
 3 const int N = 50010; 
 4 
 5 int a[N];
 6 int n,t=1;
 7 long long ans;
 8 
 9 void work(int k)
10 {
11     int tmp = a[k-1] + a[k];    //合并a和它前面的 
12     ans += tmp;
13     for(int i=k;i<t-1;++i)
14     {
15         a[i] = a[i+1];
16     } 
17     t--;
18     int j = 0;
19     for(j=k-1;j>0 && a[j-1]<tmp;--j)    //往前面找 
20     {
21         a[j] = a[j-1];
22     }
23     a[j] = tmp;
24     while(j>=2 && a[j]>=a[j-2])
25     {
26         int d = t-j;
27         work(j-1);
28         j = t-d;
29     }
30 }
31 int main()
32 {
33     scanf("%d",&n);
34     for(int i=0;i<n;++i)  //注意限制条件 
35     {
36         scanf("%d",&a[i]);
37     }
38     for(int i=1;i<n;++i)  //注意限制条件 
39     {
40         a[t++] = a[i] ;
41         while(t>=3 && a[t-3]<=a[t-1]) work(t-2);
42     }
43     while(t>1) work(t-1);
44     printf("%lld",ans);
45     return 0;
46 }