poj1738 An old Stone Game 石子合并(归并) GarsiaWachs算法

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

1
100
3
3 4 3
4
1 1 1 1
0
      

Sample Output

0
17
8      

题意: 石子合并问题, 将相邻两堆石子合并, 每次得分是合并成新的一堆石子个数, 最后累加最小值.

解题思路:

      1. 这类题目一开始想到是DP, 设dp[i][j]表示第i堆石子到第j堆石子合并最小得分.

         状态方程: dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

         sum[i]表示第1到第i堆石子总和. 递归记忆化搜索即可.

      2. 不过此题有些不一样, 1<=n<=50000范围特大, dp[50000][50000]开不到这么大数组.

         问题分析:

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

              的后面是不影响结果.

#include <stdio.h> 
#define MAX 55555

int a[MAX],n,num,result;

void combine(int k)
{
	int i,j;
 	int temp=a[k]+a[k-1];
 	result+=temp;
 	for(i=k;i<num-1;i++)
  		a[i]=a[i+1];
 	num--;
 	for(j=k-1;j>0 && a[j-1]<temp;j--)
  		a[j]=a[j-1];
 	a[j]=temp;
 	while(j>=2 && a[j]>=a[j-2])
 	{
  		int d=num-j;
  		combine(j-1);
  		j=num-d;
 	}
}

int main()
{
	int i;
 	scanf("%d",&n);
  	if(n==0)	return 0;
  	for(i=0;i<n;i++)
   		scanf("%d",&a[i]);
  	num=1;
  	result=0;
  	for(i=1;i<n;i++)
  	{
   		a[num++]=a[i];
   		while(num>=3 && a[num-3]<=a[num-1])
    		combine(num-2);
  	}
	while(num>1)	combine(num-1);
  	printf("%d\n",result);
 	return 0;
}