题目链接

https://www.luogu.com.cn/problem/P1880

解题思路

区间dp+处理环。
区间dp：，是因为你得从区间的长度入手，先把全部区间长度为1的得分算出来，才能算区间长度为2的，以此类推（应该可以记忆化）
处理环：可以通过取模的方式处理，但那样过于繁琐。因此，我们直接再复制一段区间，这样就很像构成了个环。
为什么这么处理就行？环和线唯一区别就在于线首和线尾元素不相邻，没法合并，把线扩大到两倍，就可以实现原线首与原线尾相邻。比如 1 2 3 4，1和4不相邻，通过翻倍 1 2 3 4 1 2 3 4，1与4可以相邻。
同时应该注意到，我们最后要取长度为n的区间，如果取区间 2 3 4 1，尽管1和4相邻了，但是1和2却不相邻了；如果取区间 3 4 1 2，尽管1和4，1和2相邻了，但是2和3却不相邻了。
为了解决这个问题，我们遍历区间头元素，找到所有情况中能取到的最大/最小值就行了，比如1 2 3 4构成一个环，先翻倍得到1 2 3 4 1 2 3 4，再求出1 2 3 4、2 3 4 1、3 4 1 2、4 1 2 3这四个情况（也是全部情况）里得分的最大值，即最终最大值，最小值即最终最小值。（所有情况莫过于1，4不邻，1，2不邻，2，3不邻，3，4不邻）

AC代码

#include<bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d",x)
using namespace std;
const int N=300;
const int inf=0x3f3f3f3f;
int mx[N][N],mn[N][N];//mx[i][j]表示已经将i到j区间的石子合并完成，此区间的得分最大值；同理，mn表示最小。注意区分与sum[j]-sum[i-1]的区别，sum[j]-sum[i-1]表示的是合并操作的得分，而mn，mx是已得分数
int sum[N],a[N],tmp,n;
int minn=inf,maxx;
int main(){
    sc(n);
    for(int i=1;i<=n;i++) sc(a[i]),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) sum[i+n]=sum[i+n-1]+a[i];

    /*
    //大佬题解，牛币啊，不知道为什么，虽然输入没结束，但是直接AC。果然我已经菜到连输入都看不懂了。 
    for(int i=1;i<=n+n;i++)  
    {  
        scanf("%d",&a[i]);  
        a[i+n]=a[i];  
        sum[i]=sum[i-1]+a[i];  
    }  
    */
    for(int len=2;len<=n;len++)
        for(int L=1;L<n+n;L++){
            int R=L+len-1;
            if(R>n+n) break;
            mn[L][R]=inf;
            for(int mid=L;mid<R;mid++){
                mn[L][R]=min(mn[L][R],mn[L][mid]+mn[mid+1][R]+sum[R]-sum[L-1]);
                mx[L][R]=max(mx[L][R],mx[L][mid]+mx[mid+1][R]+sum[R]-sum[L-1]);
            }        
        }

    for(int i=1;i<=n;i++){
        minn=min(minn,mn[i][i+n-1]);
        maxx=max(maxx,mx[i][i+n-1]);
    }

    pr(minn);
    printf("\n");
    pr(maxx);
}