代码就是P1775略微做了点修改

验证码：cdtj（抄的题解？然而并没有

//2023/7/7
//别着急，先通读一遍题目
//别忘了开long long
//写完先看一遍怎么降复杂度
//要么开全局变量要么给定初值
//想想看，有什么情况需要特判
//看看数组开的够不够大
//std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int MAXN=110;
int num,ans;
int sum[MAXN],dp[MAXN][MAXN],a[MAXN];
int pd[MAXN][MAXN];
int main()
{
	int n; 
	cin>>n;
	for (int i=1;i<=n;i++)	cin>>a[i];
	memset(dp,0x3f,sizeof(dp));
	memset(pd,0xcf,sizeof(pd));
	for (int i=1;i<=n;i++){
		dp[i][i]=0;
		pd[i][i]=0;
		sum[i]=sum[i-1]+a[i];
	}
	for (int len=2;len<=n;len++){
		for (int l=1;l<=n-len+1;l++){
			int r=l+len-1;
			for (int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
				pd[l][r]=max(pd[l][r],pd[l][k]+pd[k+1][r]);
			}
			dp[l][r]+=sum[r]-sum[l-1];
			pd[l][r]+=sum[r]-sum[l-1];
		}
	}
	cout<<dp[1][n]<<'\n';
	cout<<pd[1][n]<<'\n';
	return 0;
}