记录编号	248817	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-11 15:17:41	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define sum(i,j) (a[j]-a[(i)-1])
using namespace std;
namespace mine{
	int c,x,a[110],i,j;
	bool neg;
	inline int getint(){
		x=neg=0;
		do c=getchar();while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=getchar();
		}
		for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline int fgeti(FILE* fin){
		x=neg=0;
		do c=fgetc(fin);while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=fgetc(fin);
		}
		for(;c>='0'&&c<='9';c=fgetc(fin))x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline void putint(int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)putchar(a[j]);
	}
	inline void fputi(FILE* fout,int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void fputi(int x,FILE* fout){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void put(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
	}
	inline void fput(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void fput(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void puts(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
		putchar('\n');
	}
	inline void fputs(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
	inline void fputs(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
}

const int maxn=210;
int f[maxn][maxn],g[maxn][maxn],s[maxn][maxn],a[maxn],n;
int MAIN();
int haha=MAIN();
int main(){;}
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
#endif
	n=mine::getint();
	for(int i=1;i<=n;i++)a[i]=a[i+n]=mine::getint();
	a[0]=0;
	for(int i=1;i<=(n<<1);i++){
		a[i]+=a[i-1];
		s[i][i]=i;
		f[i][i]=g[i][i]=0;
	}
	for(int d=2;d<(n<<1);d++)for(int i=1;i<=(n<<1)-d+1;i++){//d为区间长度,i为起始点
		int j=i+d-1;
		f[i][j]=max(f[i][i]+f[i+1][j],f[i][j-1]+f[j][j])+sum(i,j);
		int temp=0x7fffffff;
		for(int k=s[i][j-1];k<=s[i+1][j];k++)if(g[i][k]+g[k+1][j]<temp){
			s[i][j]=k;
			temp=g[i][k]+g[k+1][j];
		}
		g[i][j]=temp+sum(i,j);
	}
	int mx=0,mn=0x7fffffff;
	for(int i=1;i<=n;i++){
		mx=max(mx,f[i][i+n-1]);
		mn=min(mn,g[i][i+n-1]);
	}
	return printf("%d\n%d",mn,mx);
}