POJ 1738：An old Stone Game 石子归并(GarsiaWachs算法)

An old Stone Game

Time Limit: 5000MS		Memory Limit: 30000K
Total Submissions: 2981		Accepted: 796

Description

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

Sample Output

0
17
8

还是石子归并问题，但是因为现在石子有50000堆，就需要开int[50000][50000]的数组，无论空间还是时间都可能挂掉，就得寻求更好的方法。

GarsiaWachs算法是从第一个石堆开始找符合stone[k-1]<stone[k+1]的石堆k，然后合并k-1与k堆，再向前找j堆石子，满足stone[j]>stone[k]+stone[k-1],插入到石堆j的后面。然后重新寻找。

我觉得GarsiaWachs算法的想法就是把石子就想象成是三堆，k-1 k k+1堆，如果stone[k-1]<stone[k+1]，那么一定是先合并k-1与k堆是合理的，之后把合并的堆插入到stone[j]的后面，是把stone[j+1]与stone[k-2]看成一个整体stone[m],所以现在就是stone[j],stone[m],(stone[k-1]+stone[k])，因为stone[k-1]+stone[k]<stone[j],所以插入到stone[j]后面是希望(stone[k-1]+stone[k])与stone[m]先合并，这样就不断地都是最优解，得到的结果也就是最优结果。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int n,ans,stone_num;
int stone[50005];

void combine(int t)
{
	int i,j;
	int temp = stone[t] + stone[t - 1];
	ans += temp;
	
	for (int i = t; i < stone_num - 1; i++)
		stone[i] = stone[i + 1];

	stone_num--;
	for (j = t - 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 dis = stone_num - j;
		combine(j - 1);
		j = stone_num - dis;
	}
}

int main()
{
	int i;

	while (scanf("%d", &n)!=EOF)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d", stone+i);
		}
		stone_num = 1;
		ans = 0;

		for (i = 1; i < n; i++)
		{
			stone[stone_num++] = stone[i];

			while (stone_num >= 3 && stone[stone_num - 3]<=stone[stone_num - 1])
			{
				combine(stone_num - 2);
			}
		}
		while (stone_num > 1)combine(stone_num - 1);
		cout << ans << endl;
	}
	return 0;
}