思路

线性相邻合并且只输出最小值，区别圆形双目标NOI版本；区间分割枚举并加区间总和。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<int>s(n+1);for(int i=1,x;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}vector<vector<int>>d(n,vector<int>(n));for(int len=2;len<=n;len++)for(int l=0;l+len<=n;l++){int h=l+len-1;d[l][h]=INT_MAX;for(int k=l;k<h;k++)d[l][h]=min(d[l][h],d[l][k]+d[k+1][h]+s[h+1]-s[l]);}cout<<d[0][n-1]<<'\n';}