记录编号	241664	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2016-03-26 08:07:36	内存使用	0.39 MiB

#include<cstdio>
#include<cstring>
const int maxn=105;
int s[maxn*2],sum[maxn*2];
int f[maxn*2][maxn*2];
int n,n2;
int low(int a,int b){
	return a<b?a:b;
}
int high(int a,int b){
	return a>b?a:b;
}
int dp(int cmp(int,int),int init){
	memset(f,init,sizeof(f));
	for(int i=1;i<=n2;++i)f[i][i]=0;
	for(int k=1;k<n;++k){//枚举“区间长度-1” 
		for(int i=1;i+k<=n2;++i)//i+k：区间终点 
		{
			int j=i+k;
			for(int p=i;p<j;++p){
				f[i][j]=cmp(f[i][j],f[i][p]+f[p+1][j]+sum[j]-sum[i-1]);
//			if(init==127)printf("f[%d][%d]cmp(f[%d][%d]+f[%d][%d]+s[%d]-s[%d]))==%d\n",i,j,i,p,p+1,j,j,i-1,f[i][j]);
			}
		}
	}
	int ans=(init==0)?0:1<<25;
	for(int i=1;i+n-1<=n2;++i)ans=cmp(ans,f[i][i+n-1]);
	return ans;
}
int main(){
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
	scanf("%d",&n);n2=n*2;
	for(int i=1;i<=n;++i){
		scanf("%d",s+i);
		sum[i]=sum[i-1]+s[i];
	}
	for(int i=n+1;i<=n2;++i){
		s[i]=s[i-n];
		sum[i]=sum[i-1]+s[i];
	}
//	for(int i=0;i<=n;++i)printf("%d ",sum[i]);
//	printf("\n");
	printf("%d\n%d\n",dp(low,127),dp(high,0));
/*	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)printf("%d ",f[i][j]);
		printf("\n");
	}*/
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
8
66 88 180 175 111 151 51 3

ans:
2294
4561
*/