这题没什么好说的吧。。记录一下自己的一点想法
区间DP是从小区间得出最优解，大区间再合并小区间求最优解的。
对于这题，我们不妨设
[f[i][j]表示为区间i，j的最优解
]
如果我们通过枚举区间端点i，j来转移，显然是不行的。因为这样不满足小区间到大区间的要求，
会这样算
[f[1][1] qquad f[1][2] qquad f[1][3] cdots
]
所以我们要变通思路，小区间，那么我们就枚举区间长度，在枚举区间左端点
就会这样算
[f[1][1] qquad f[2][2] qquad f[3]f[3] cdots
]
my code:
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
inline char gt() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read(T &x) {
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
if(x < 0) x = -x, putchar('-');
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
while(num) putchar(ch[num--]);
putchar('
');
}
const int N = 207;
int a[N];
int sum[N], n;
int f[N][N], ff[N][N];
int main() {
read(n);
rep(i, 1, n) {
read(a[i]);
a[i + n] = a[i];
sum[i] = sum[i - 1] + a[i];
}
rep(i, n + 1, 2 * n)
sum[i] = sum[i - 1] + a[i];
memset(f, 0x3f, sizeof f);
rep(i, 1, n * 2) f[i][i] = 0;
rep(len, 2, n)
for(register int l = 1, r = l + len - 1; l + len - 1 <= 2 * n; ++l, r++)
{
rep(k, l, r - 1) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
ff[l][r] = max(ff[l][r], ff[l][k] + ff[k + 1][r] + sum[r] - sum[l - 1]);
}
}
int ans1 = INT_MAX, ans2 = INT_MIN;
rep(i, 1, n) {
ans1 = min(ans1, f[i][i + n - 1]);
ans2 = max(ans2, ff[i][i + n - 1]);
}
out(ans1);
out(ans2);
return 0;
}