1. 题目

传送门＝￣ω￣＝

2. 题解

此题还是很简单的。
如果是个链。。。
设 $f1[i][j],f2[i][j]$分别为区间 $[i,j]$合并后的最大值、最小值。不难得到递推式：
$f1[i][j]=max\{f1[i][k]+f1[k+1][j]|i<=k<j\}$
$f2[i][j]=min\{f2[i][k]+f2[k+1][j]|i<=k<j\}$

嗯，题目是个环。
对于环，常用的方法就是把环切开成一条链，然后把链复制一遍，两个链首尾相接，接成一条长为 $2×n$的链。
然后再跑上面的递推。
最后答案：
最大值：$ans1=max\{f[i][i+n-1]|1<=i<=n\}$

代码：

#include <bits/stdc++.h>
using namespace std;
int n,n2,arr[205],sum[205],f1[205][205],f2[205][205],ans1,ans2=INT_MAX;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]),arr[i+n]=arr[i];
    n2=(n<<1),memset(f2,127,sizeof(f2));
    for(int i=1;i<=n2;i++)f2[i][i]=0,sum[i]=sum[i-1]+arr[i];
    for(int l=2;l<=n;l++)
        for(int i=1;i+l-1<=n2;i++)
        {
            for(int j=i;j<i+l-1;j++)
                f1[i][i+l-1]=max(f1[i][i+l-1],f1[i][j]+f1[j+1][i+l-1]),
                f2[i][i+l-1]=min(f2[i][i+l-1],f2[i][j]+f2[j+1][i+l-1]);
            f1[i][i+l-1]+=sum[i+l-1]-sum[i-1],f2[i][i+l-1]+=sum[i+l-1]-sum[i-1];
        }
    for(int i=1;i<=n;i++)
        ans1=max(ans1,f1[i][i+n-1]),ans2=min(ans2,f2[i][i+n-1]);
    printf("%d\n%d\n",ans2,ans1);
    return 0;
}