记录编号	106546	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-06-14 19:26:53	内存使用	0.60 MiB

#include <cstdio>

#define  maxhalf  107e7
#define  maxn     201

int n ;
int ansmi = 0x7fffffff ;
int ansma = 0 ;
int a[maxn];
int sum[maxn]={0};
int fma[maxn][maxn]={0};
int fmi[maxn][maxn] ;

void In()
{
	scanf("%d", &n ) ;
	for (int i = 1 ; i <= n ; i ++ )
	{
		scanf("%d", &a[i] ) ;
		a[i+n] = a[i] ;
		sum[i] = sum[i-1] + a[i] ;
	}
	for (int i = n + 1  ; i <= 2*n ; i ++ ) sum[i] = sum[i-1] + a[i] ;
}

void Dp()
{
	for (int d = 2 ; d <= n ; d ++ )
	{
		for (int i = 1 ; i <= 2*n-d+1 ; i ++ )
		{
			int j = i+d-1 , t ;
			fmi[i][j] = maxhalf ;
			t = fma[i][i]+fma[i+1][j] ;
			if (t > fma[i][j]) fma[i][j] = t ;
			t = fma[i][j-1]+fma[j][j] ;
			if (t > fma[i][j]) fma[i][j] = t ;
			for (int k = i ; k < j ; k ++ )
			{
				t = fmi[i][k]+fmi[k+1][j] ;
				if (t < fmi[i][j]) fmi[i][j] = t ;
			}
			fma[i][j] += sum[j]-sum[i-1] ;
			fmi[i][j] += sum[j]-sum[i-1] ;
		}
	}
}

void Out()
{
	for (int i = 1 ; i <= n ; i ++ )
	{
		if (fmi[i][i+n-1] < ansmi) ansmi = fmi[i][i+n-1] ;
		if (fma[i][i+n-1] > ansma) ansma = fma[i][i+n-1] ;
	}
	printf("%d\n%d\n",ansmi,ansma);
}

int main()
{
	freopen("stone2.in" ,"r",stdin );
	freopen("stone2.out","w",stdout);
	In() ;
	Dp() ;
	Out() ;
	
	return 0 ;
}