An old Stone Game
There is an old stone game.At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
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 input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero.
Output
For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.
Sample Input
1
100
3
3 4 3
4
1 1 1 1
0
Sample Output
0
17
8
Source
题目类型：石子合并GarsiaWachs算法
算法分析：直接使用GarsiaWachs算法求解即可，最好使用平衡树优化，否则直接使用O(n ^ 2)的算法很可能会TLE!!!!!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 500000 + 66; int stone[maxn]; int n, t, ans; void Combine (int k) { int temp = stone[k] + stone[k-1]; ans += temp; 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] < temp; j--) stone[j] = stone[j-1]; stone[j] = temp; while (j >= 2 && stone[j] >= stone[j-2]) { int d = t - j; Combine (j - 1); j = t - d; } } int main() { // freopen ("aaa.txt", "r", stdin); while (cin >> n) { if (n == 0) break ; for (int i = 0;i < n; i++) cin >> 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); cout << ans << endl; } return 0; } |
- « 上一篇：poj1703
- poj1751：下一篇 »