[NOI1995]石子合並

在一個園形操場的四周擺放N堆石子,現要將石子有次序地合並成一堆.規定每次只能選相鄰的2堆合並成新的一堆，並將新的一堆的石子數，記為該次合並的得分。
試設計出1個算法,計算出將N堆石子合並成1堆的最小得分和最大得分.

/*
圓的話就用2*n-1,即只有n種情況; 
*/
#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>
const int INF=(1<<31)-1; 
int s[201],d[201][201],b[201][201],a[101]; 
int main(int argc, char *argv[])
{
	int i,j,k,n,r,t,t1,m;
	cin>>n; s[0]=0; 
	memset(d,0,sizeof(d)); 	memset(b,0,sizeof(b)); 
	for(i=1;i<=n;i++) {cin>>a[i]; s[i]=s[i-1]+a[i];}
	for(i=1;i<n;i++) s[n+i]=s[n+i-1]+a[i]; m=n,n=2*n-1; 
	for(r=2;r<=n;r++)
	for(i=1;i<=n-r+1;i++)
	{j=i+r-1; t=INF; t1=0; 
	for(k=i;k<=i+r-2;k++)
		t= min(t,d[i][k]+d[k+1][j]+s[j]-s[i-1]), t1= max(t1,b[i][k]+b[k+1][j]+s[j]-s[i-1]);
	    d[i][j]=t; b[i][j]=t1; 
	}
	t=INF; t1=0; 
	for(i=1;i<=m;i++) 
	{
	if(t>d[i][m+i-1]) t=d[i][m+i-1];
	if(t1<b[i][m+i-1]) t1=b[i][m+i-1];
	}
	if(m==1) t=a[1],t1=a[1]; 
	cout<<t<<endl<<t1<<endl; 
	return 0;
}