题目
首先断环为链，然后我们发现对于求最小值，这是一个裸的四边形不等式优化dp。
而对于最大值，我们可以发现(s_{i,j}=l or r-1)。
#include<bits/stdc++.h>
#define R register
using namespace std;
int a[2001],s[2001],f[2001][2001],g[2001][2001],p[2001][2001],n,minn=1000000,maxn;
inline int read()
{
R int x=0;
R char c=getchar();
while(c>'9'||c<'0')
c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int main()
{
n=read();
for(R int i=1;i<=n;i++)
a[i]=a[n+i]=read(),s[i]=s[i-1]+a[i],p[i][i]=i;
for(R int i=n+1;i<=(n<<1);i++)
s[i]=s[i-1]+a[i],p[i][i]=i;
for(R int i=(n<<1)-1;i;i--)
for(R int j=i+1;j<=(n<<1);j++)
{
g[i][j]=max(g[i][j-1],g[i+1][j])+s[j]-s[i-1];
int tmp=10000000;
for(R int k=p[i][j-1];k<=p[i+1][j];k++)
if(f[i][k]+f[k+1][j]+s[j]-s[i-1]<tmp)
tmp=f[i][k]+f[k+1][j]+s[j]-s[i-1],p[i][j]=k;
f[i][j]=tmp;
}
for(R int i=1;i<=n;i++)
minn=f[i][i+n-1]<minn? f[i][i+n-1]:minn,maxn=g[i][i+n-1]>maxn? g[i][i+n-1]:maxn;
printf("%d
%d",minn,maxn);
}