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;
}