#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=305;
const int INF=0x3f3f3f3f;
int dp[N][N];
int a[N];
int sum[N];
int minn=INF;
int maxx;
int dp1[N][N];
int main(){
	cin>>n;
	memset(dp,INF,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;i++){
		dp[i][i]=0;
		sum[i]=sum[i-1]+a[i];
	}
	//区间dp模板
	for(int len=2;len<=n;len++){
    	for(int i=1;i<=2*n-len+1;i++){
       		int j=i+len-1;
       		for(int k=i;k<=j-1;k++){ 
         	    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
         	    dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
     		}
   		}
	}
	for(int i=1;i<=n;i++){
		minn=min(minn,dp[i][i+n-1]);
		maxx=max(maxx,dp1[i][i+n-1]);
	}
	cout<<minn<<endl<<maxx; 
	return 0;
}

#include<iostream>
using namespace std;
const int MAXN = 210;
const int INF = 114514;
int n,a[MAXN],b[MAXN];
int dp1[MAXN][MAXN];
int dp[MAXN][MAXN];
int maxx = -INF;
int minn = INF;
int pre[MAXN];
int main() {
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	for (int i = 0;i < 2 * n;i++) {
		b[i] = a[i % n];
	}
	for (int i = 0;i < 2 * n;i++) {
		pre[i + 1] = pre[i] + b[i];
	}
	for (int i = 0;i < 2 * n;i++) {
		for (int j = 0;j < 2 * n;j++) {
			dp[i][j] = INF;
			dp1[i][j] = -INF;
		}
		dp[i][i] = 0;
		dp1[i][i] = 0;
	}
	for (int len = 2;len <= n;len++) {
		for (int i = 0;i + len - 1 < 2 * n;i++) {
			int j = i + len - 1;
			int ij = pre[j + 1] - pre[i];
			for (int k = i;k < j;k++) {
				if (dp[i][k] != INF && dp[k + 1][j] != INF) {
					dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + ij);
				}
				if (dp1[i][k] != -INF && dp1[k + 1][j] != -INF) {
					dp1[i][j] = max(dp1[i][j],dp1[i][k] + dp1[k + 1][j] + ij);
				}
			}
		}
	}
	for (int i = 0;i < n;i++) {
		minn = min(minn,dp[i][i + n - 1]);
		maxx = max(maxx,dp1[i][i + n - 1]);
	}
	cout << minn << endl;
	cout << maxx << endl;
	return 0;
}

#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i + n] = a[i]; // 处理环形数组
    }

    // 计算前缀和数组
    vector<long long> prefix(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; ++i) {
        prefix[i] = prefix[i - 1] + a[i - 1];
    }

    // 初始化动态规划数组
    const long long INF = 1e18;
    vector<vector<long long> > dp_min(2 * n, vector<long long>(2 * n, INF));
    vector<vector<long long> > dp_max(2 * n, vector<long long>(2 * n, -INF));

    for (int i = 0; i < 2 * n; ++i) {
        dp_min[i][i] = 0;
        dp_max[i][i] = 0;
    }

    // 动态规划填表
    for (int len = 2; len <= n; ++len) { // 合并的区间长度
        for (int i = 0; i <= 2 * n - len; ++i) { // 区间起点
            int j = i + len - 1; // 区间终点
            long long sum_ij = prefix[j + 1] - prefix[i];

            // 枚举分割点k
            for (int k = i; k < j; ++k) {
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum_ij);
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum_ij);
            }
        }
    }

    // 寻找所有可能的起点中的最优解
    long long min_score = INF, max_score = -INF;
    for (int i = 0; i < n; ++i) {
        int j = i + n - 1;
        min_score = min(min_score, dp_min[i][j]);
        max_score = max(max_score, dp_max[i][j]);
    }

    cout << min_score << endl;
    cout << max_score << endl;

    return 0;
}

没见过吧，那就点赞再走。

求求了QAQ

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <vector>
using namespace std;
#define long long LL
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;
int n,a[N],dp[N][N],minn = INF,sum[N],dp1[N][N],maxx;
int main(){
	cin >> n;
	memset(dp,INF,sizeof(dp));
	for (int i = 1;i<=n;i++){
		cin >> a[i];
		a[i+n] = a[i];
	}
	for (int i = 1;i<=2*n;i++){
		sum[i] = sum[i-1] + a[i];
		dp[i][i] = 0;
	}
	for (int i = 2;i<=n;i++){
		for (int j = 1;j<=2*n-i+1;j++){
			int endx = j + i - 1;
			for (int k = j;k<endx;k++){
				dp[j][endx] = min(dp[j][endx],dp[j][k] + dp[k+1][endx] + sum[endx] - sum[j-1]);
				dp1[j][endx] = max(dp1[j][endx],dp1[j][k] + dp1[k+1][endx] + sum[endx] - sum[j-1]);
			}
		}
	}
	for (int i = 1;i<=n;i++){
		minn = min(minn,dp[i][i+n-1]);
		maxx = max(maxx,dp1[i][i+n-1]);
	}
	cout << minn << endl << maxx;
	return 0;
}

'''和上一题十分类似，简单加点东西就好了。这里不多做解释。代码比较好理解。

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int dp[505][505];
int f[505][505];
int a[305];
int sum[N];
int main(){

	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		a[i + n] = a[i];
	}
	for(int i=1; i<=2*n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	for(int k = 2; k <= n; k++)
	{
		for(int l = 1; l + k - 1 <= 2 * n; l++)
		{
			int r = l + k - 1;
			f[l][r] = INF;
			for(int i = l; i < r; i++)
			{
				dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r] + sum[r] - sum[l - 1]);
				f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1]);
			}
		}
	}
	int minn = INF;
	int maxx = 0;
	for(int i = 1; i <= n; i++)
	{
		maxx = max(maxx, dp[i][i + n - 1]);
		minn = min(minn, f[i][i + n - 1]);
	}
	cout<<minn<<endl;
	cout<<maxx<<endl;
	

	return 0;
}