诈骗题，看着像贪心，实际上是 DP
对贪心的 hack：
6
3 4 6 5 4 2
如果使用贪心法求最小得分，应该是如下的合并步骤：
第一次合并 3 4 6 5 4 2 2,3合并得分是５
第二次合并 5 4 6 5 4 5,4合并得分是9
第三次合并 9 6 5 4 5,4合并得分是9
第四次合并 9 6 9 9,6合并得分是15
第五次合并 15 9 15,9合并得分是24
总得分＝5＋9＋9＋15＋24＝62
但是如果采用如下合并方法，却可以得到比上面得分更少的方法：
第一次合并 3 4 6 5 4 2 3,4合并得分是7
第二次合并 7 6 5 4 2 7,6合并得分是13
第三次合并 13 5 4 2 4,2合并得分是6
第四次合并 13 5 6 5,6合并得分是11
第五次合并 13 11 13,11合并得分是24
总得分＝7＋13＋6＋11＋24＝61
——by TJ-Kevin_Wa
以最小为例：
对于这个区间 DP，\(dp_{i,j}\) 表示 \([i,j]\) 中最小的花费，使用 DFS 转移，避免复杂的顺序考虑。
方程：
\[dp_{i,j} = \begin{cases} 0,i = j \\ \min_{k=i}^{j-1} dp_{i,k} + dp_{k+1,j}+\sum_{l=i}^{j}a_l\\ \end{cases} \]代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[210];
int dp1[210][210],dp2[210][210];
int ans1,ans2;
int dfs1(int l,int r){
if(dp1[l][r])return dp1[l][r];
if(l==r)return 0;
int ret=2147483647;
for(int i=l;i<r;i++){
ret=min(ret,dfs1(l,i)+dfs1(i+1,r));
}
for(int i=l;i<=r;i++){
ret+=a[i];
}
return dp1[l][r]=ret;
}
int dfs2(int l,int r){
if(dp2[l][r])return dp2[l][r];
if(l==r)return 0;
int ret=0;
for(int i=l;i<r;i++){
ret=max(ret,dfs2(l,i)+dfs2(i+1,r));
}
for(int i=l;i<=r;i++){
ret+=a[i];
}
return dp2[l][r]=ret;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
a[n+i]=a[i];
}
dfs1(1,2*n);
dfs2(1,2*n);
ans1=2147483647;
for(int i=1;i<=n;i++){
ans1=min(ans1,dp1[i][n+i-1]);
ans2=max(ans2,dp2[i][n+i-1]);
}
cout<<ans1<<endl<<ans2;
return 0;
}