记录编号	308188	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	牧殇	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-09-17 09:53:38	内存使用	0.65 MiB

#include<cstdio>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int Read()
{
	char ch;int x,f=1;
	while(ch=getchar(),ch<'0' || ch>'9') if(ch=='-')	f=-1;
	x=ch-48;
	while(ch=getchar(),ch<='9' && ch>='0' )	x=x*10+ch-48;
	return x*f;	
}
int main()
{
	freopen("stone2.in","r",stdin);
    freopen("stone2.out","w",stdout);
	int n=Read(),f[205][205],c[205][205],a[205],s[205][205]={0},ans=0,num=0x7ffff;
	for(int i=1;i<=n;++i)
	{
		a[i]=Read();
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;++i)
	{
		f[i][i]=0;
		c[i][i]=a[i];
		for(int j=i+1;j<=2*n;++j)
			c[i][j]=c[i][j-1]+a[j];
	}
	for(int i=0;i<=2*n;++i)s[i][i]=i;//是2n 不是n！！！！！！！！！！ 
	for(int l=2;l<=n;++l)
		for(int i=1;i<=2*n-l+1;++i)
		{
			int j=l+i-1;
			f[i][j]=1000000000;
			for(int k=s[i][j-1];k<=s[i+1][j];++k)
			{
				if(f[i][j]>f[i][k]+f[k+1][j]+c[i][j]){
					f[i][j]=f[i][k]+f[k+1][j]+c[i][j];
					s[i][j]=k;//不是k+1！ 
				}
			}
			if(l==n)	num=min(num,f[i][j]);
		}
		for(int l=2;l<=n;++l)
		for(int i=1;i<=2*n-l+1;++i)
		{
			int j=l+i-1;
			f[i][j]=0;
			f[i][j]=max(f[i+1][j]+c[i][j],f[i][j-1]+c[i][j]);
			if(l==n)	ans=max(ans,f[i][j]);	 
		}
	printf("%d\n%d",num,ans);
	//while(1);
	return 0; 
}