题目大意
环形队列上有 $n$ 堆石子，可以把相邻的两堆合成一堆，每次合并的得分是新一堆的石子数。
求最终分数的最小值和最大值。
分析
考虑 $dp(i,j)$ 是将区间 $[i,j]$ 的石子全部合并的最大值。于是状态转移方程为
$$ dp(i,j) = \max_{i \leqslant k \leqslant j}(dp(i,k) + dp(k+1,j) + s(i,j)) $$
其中 $s(i,j)$ 是 $[i,j]$ 中所有石子数。
然而不能通过先 $i$ 再 $j$ 再 $k$ 的循环来递推，运算顺序值得注意。
细节：前缀和、循环开两倍。
int dmax[205][205], dmin[205][205];
int f[205], s[205];
int main() {
int n = rr();
for (ll i = 1; i <= n; i++)
f[i + n] = f[i] = rr();
for (ll i = 1; i <= n * 2; i++)
s[i] = s[i - 1] + f[i];
for (ll len = 2; len <= n; len++) {
for (ll i = 1; i <= 2 * n - len + 1; i++) {
int j = i + len - 1;
int tmax = 0, tmin = 0x3f3f3f3f;
int ss = s[j] - s[i - 1];
for (ll k = i; k <= j - 1; k++) {
tmax = max(tmax, dmax[i][k] + dmax[k + 1][j] + ss);
tmin = min(tmin, dmin[i][k] + dmin[k + 1][j] + ss);
}
dmax[i][j] = tmax;
dmin[i][j] = tmin;
}
}
int mmin = 0x3f3f3f3f, mmax = 0;
for (ll p = 0; p <= n - 1; p++) {
mmin = min(mmin, dmin[p + 1][p + n]);
mmax = max(mmax, dmax[p + 1][p + n]);
}
printf("%d\n%d\n", mmin, mmax);
return 0;
}