这是一个年代久远的区间dp (好像以前培训的时候讲了，但是现在才想起来去A)
区间dp常用状态：
f[i][j]：以i为左端点，j为右端点的最优解
第一层循环枚举区间长度，第二层循环枚举起点，第三层枚举中间的断点
（貌似写到这里这个题就写完了）
特点：
问题能转换为两两合并的问题（such as 能量项链，石子合并），当然可以再bt一点弄分解问题
步入正题
我们设f[i][j]为合并i到j的最大得分，g[i][j]为最小得分（代码里会出现一些奇怪的东西）。要合并i到j,则对于i，j之间的一个k来说，肯定是先合并了i到k，再合并k+1到 j。
而且合并完了还要计算合并i到k与合并k+1到j的得分。得分就是s[i](第i堆石子的个数)+s[i+1]+........+s[j]，为了节省时间，我们用前缀和的形式计算，即sum[i]=s[1]+s[2]+...+s[i],那么得分也就是sum[j]-sum[i-1].
综上，f[i][j]=max(f[i][k],f[k+1][j])+sum[j]-sum[i-1](i<=k<j)
g[i][j]=min(g[i][k],g[k+1][j])+sum[j]-sum[i-1](i<=k<j)
我们再来考虑边界状态
f[i][i]=0,g[i][i]=0,因为合并i到i相当于没有合并，不得分
g[i][j]=INF,(取min用),f[i][j]=0(取max用)
这个题还牵扯到环，so这时候就该扯扯环变链了
因为n与1相邻，所以我们不妨把s[n+1]设成与s[1]一样，这样就可以处理合并n和1了。
但是合并n到2,3,4...n-1呢？（注意不是2,3,4...n-1到n）
思考过后，我们发现可以使s[n+i]=s[i],这样就可以处理起点是n的情况了
这样就可以写代码了（循环顺序在开头）
（奇怪的变量名警告）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,s[209],mitsu[209][209],nobu[209][209],sum[209];//nobu是最大值，mitsu是最小值
int read()//一堆快读
{
int x=0;
bool flag=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')flag=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
if(flag)x=-x;
return x;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
s[i]=read();s[i+n]=s[i];//环变链处理
}
for(int i=1;i<=2*n;i++)
{
sum[i]=sum[i-1]+s[i];
nobu[i][i]=0;
mitsu[i][i]=0;
}
for(int len=1;len<=n;len++)
{
for(int st=1;st<2*n-len+1;st++)
{
int end=st+len;
mitsu[st][end]=214748364;
for(int k=st;k<end;k++)
{
nobu[st][end]=max(nobu[st][end],nobu[st][k]+nobu[k+1][end]);
mitsu[st][end]=min(mitsu[st][end],mitsu[st][k]+mitsu[k+1][end]);
}
nobu[st][end]+=sum[end]-sum[st-1];
mitsu[st][end]+=sum[end]-sum[st-1];
}
}
int maxn=-1,minn=214748364;
for(int i=1;i<=n;i++)//统计答案
{
maxn=max(maxn,nobu[i][i+n-1]);
minn=min(minn,mitsu[i][i+n-1]);
}
printf("%d\n%d",minn,maxn);
}
//I love Akchi Mitsuhide and Oda Nobu Naga