题目链接: https://vjudge.net/contest/537778#problem/F

题意

给出 n 堆石子，每堆有 {ai} 个石子，每次合并相邻的两堆石子可以获得这两堆石子的数量的得分。

求能够获得的得分的最大值和最小值。

1≤n≤100，0≤ai≤20。

思路

区间dp。设 dp[l][r] 为在区间 [l, r] 上能获得的最值，那么有

dp[l][r] = min/max({dp[l][k]+dp[k+1][r]})，其中 k 属于 [l, r]

这题中由于所有石子围成一圈，所以头和尾是可以合并的。这样的话需要把整个数组复制一遍，然后枚举一下不同的数列排序，比如 [1,2,3]->[2,3,1]->[3,1,2]。

用一遍记忆化搜索就可以了。

时间复杂度：O(n^3)

代码

#include <iostream>
#include <queue>
#include <climits>

#define orep(i,l,r) for(int i = (l); i < (r); ++i)
#define NL          '\n'

const int maxN = 2e2+5;
int arr[maxN];
long long mi[maxN][maxN], mx[maxN][maxN];

long long dfsMx(const int l, const int r) {
  if (mx[l][r]) { return mx[l][r]; }
  if (l == r) { return 0; }
  long long max = 0;
  orep(i, 0, r-l) {
    max = std::max(dfsMx(l, l+i) + dfsMx(l+i+1, r), max);
  }
  return mx[l][r] = max + arr[r]-arr[l-1];
}

long long dfsMi(const int l, const int r) {
  if (mi[l][r]) { return mi[l][r]; }
  if (l == r) { return 0; }
  long long min = 1ll<<62;
  orep(i, 0, r-l) {
    min = std::min(dfsMi(l, l+i) + dfsMi(l+i+1, r), min);
  }
  return mi[l][r] = min + arr[r]-arr[l-1];
}

int main() {
  int n; std::cin >> n;
  orep(i, 1, n+1) { std::cin >> arr[i]; arr[i+n] = arr[i]; arr[i] += arr[i-1]; }
  long long r1=1ll<<62, r2=0;
  orep(i, 1, n+1) {
    arr[i+n] += arr[i+n-1];
    r1 = std::min(dfsMi(i, i+n-1), r1);
    r2 = std::max(dfsMx(i, i+n-1), r2);
  }

  std::cout << r1 << NL;
  std::cout << r2 << NL;

  return 0;
}