救我！！玄关

#include<bits/stdc++.h>
using namespace std;
int n,a[110],s[110],dp[110][110];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	} 
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			dp[l][r]=1e9;
			for(int k=l;k<=r-1;k++){
				dp[l][r]=min(dp[l][k]+dp[k+1][r]+s[r]-s[l-1],dp[l][r]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	memset(dp,0,sizeof(dp));
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			for(int k=l;k<=r-1;k++){
				dp[l][r]=max(dp[l][k]+dp[k+1][r]+s[r]-s[l-1],dp[l][r]);
			}
		}
	}
	cout<<dp[1][n];
}