石头合并问题.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
using namespace std;

//石头合并问题 PKU 1086 动态规划
/*
输入：
4
4  1  2  3

输出：
*/
#define MAX 1000000000
int a[202];//每个石头的重量
long f[202][202];//f[i][j]，第i个石头分到第j个石头合并的最小代价
long sum[202][202];//sum[i][j],第i个石头到第j个石头的重量之和

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			printf("%3d",f[i][j]);
		cout<<endl;
	}
	cout<<endl;
	system("pause");
}

void cal(int num)
{
	int i,j,k,min,d;
	for(i=1;i<=num;i++)
		f[i][i]=0;//不合并时的代价
	for(i=1;i<num;i++)
	{
		sum[i][i]=a[i];
		for(j=i+1;j<=num;j++)
		{
			sum[i][j]=sum[i][j-1]+a[j];
		}
	}
	sum[num][num]=a[num];
	for(d=1;d<=num-1;d++)
	{
		for(i=1;i<=num-d;i++)
		{
			j=i+d;
			min=MAX;
			//i..k为一堆石头，k+1,k+2...j为另一堆石头
			//f[i][j]为f[i][k]+f[k+1][j]+sum[i][j]的最小值(i<=j<k)
			for(k=i;k<j;k++)
				if(min>f[i][k]+f[k+1][j]+sum[i][j]) min=f[i][k]+f[k+1][j]+sum[i][j];
			f[i][j]=min;
			print(num);
		}
	}
}

int main()
{
	int num,i;
	scanf("%d",&num);
	for(i=1;i<=num;i++)
		cin>>a[i];
	cal(num);
	cout<<f[1][num]<<endl;
	return 0;
}