pebblemerging.cpp

石子合并问题的解法

// PebbleMerging.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>

int main(int argc, char* argv[])
{
	int n;
	int t;
	int m[100][99][2];
	int arr[100];
	cin>>n;
	for(int i=0;i<n;i++)                                                                                        
	{
		cin>>t;
		arr[i]=t;
		m[i][1][0]=0;
		m[i][1][1]=0;
	}
	for(int r=2;r<=n;r++)
	{
		for(i=0;i<n;i++)
		{
			int min=m[i][1][0]+m[(i+1)%n][r-1][0];
			int max=m[i][1][1]+m[(i+1)%n][r-1][1];
			int sum=arr[i];
			for(int j=2;j<r;j++)
			{
				t=m[i][j][0]+m[(i+j)%n][r-j][0];
				if(t<min)
				{
					min=t;
				}
				t=m[i][j][1]+m[(i+j)%n][r-j][1];
				if(t>max)
				{
					max=t;
				}
				sum+=arr[(i+j-1)%n];
			}
			sum+=arr[(i+r-1)%n];
			m[i][r][0]=min+sum;
			m[i][r][1]=max+sum;
		}
	}
	int min2=m[0][n][0];
	int max2=m[0][n][1];
	for(i=1;i<n;i++)
	{
		if(m[i][n][0]<min2)
		{
			min2=m[i][n][0];
		}
		if(m[i][n][1]>max2)
		{
			max2=m[i][n][1];
		}
	}
	cout<<min2<<endl;
	cout<<max2<<endl;
	return 0;
}