记录编号	246814	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-04-07 11:13:58	内存使用	0.48 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a=0,minus=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	minus=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a*minus;
}

int GetMin(int a, int b)
{
	return a<b?a:b;
}

int GetMax(int a, int b)
{
	return a>b?a:b;
}

int a[210]={0},sum[210]={0}/*前i堆的总数*/;
int f[210][210]={0};
/*f[i][j]:第i堆合并到第j堆的最优值*/

int main()
{
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
	const int N=Read();
	for(int i=1;i<=N;i++){
		a[i]=Read();
		sum[i]=sum[i-1]+a[i]; 
	}
	for(int i=N+1;i<=N*2;i++){
		a[i]=a[i-N];
		sum[i]=sum[i-1]+a[i];
	}
	
	memset(f,0x7f,sizeof(f)); 
	for(int i=1;i<=N*2;i++)	f[i][i]=0;/*一堆石子与自己不能合并*/
	for(int l=1;l<N;l++){/*l可以理解为区间长度*/
		for(int s=1;s+l<=N*2;s++){/*s是起点下标,s+l是终点,倍增*/
			int end=s+l;	
			for(int pos=s;pos<end;pos++){/*j是起点、终点之间某点下标*/
				f[s][end]=GetMin(f[s][end],f[s][pos]+f[pos+1][end]+sum[end]-sum[s-1]);
				//是这一整堆,还是从pos分开的两小堆？ 
			}
		} 
	} 
	int ans=0x7fffffff;
	for(int i=1;i+N-1<=N*2/*倍增注意,区间起点到终点*/;i++)	ans=GetMin(ans,f[i][i+N-1]);//i是起点,从起点到终点的区间,长度一定是N 
	printf("%d\n",ans);
	
	memset(f,0,sizeof(f)); 
	for(int l=1;l<N;l++){
		for(int s=1;s+l<=N*2;s++){
			int end=s+l;
			for(int pos=s;pos<end;pos++){
				f[s][end]=GetMax(f[s][end],f[s][pos]+f[pos+1][end]+sum[end]-sum[s-1]);
			}
		} 
	} 
	ans=0;
	for(int i=1;i+N-1<=N*2;i++)	ans=GetMax(ans,f[i][i+N-1]);
	printf("%d",ans);
	
	fclose(stdin);fclose(stdout);
	return 0;
}