将 nn 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数 nn 及每堆的石子数，并进行如下计算：

  • 选择一种合并石子的方案，使得做 n−1n−1 次合并得分总和最大。
  • 选择一种合并石子的方案，使得做 n−1n−1 次合并得分总和最小。

    输入格式

    第一行包含整数 nn，表示共有 nn 堆石子。
    第二行包含 nn 个整数，分别表示每堆石子的数量。

    输出格式

    输出共两行：
    第一行为合并得分总和最小值，
    第二行为合并得分总和最大值。

    数据范围

    1≤n≤2001≤n≤200

    输入样例：

    4 4 5 9 4

    输出样例：

    43 54
  1. //环形dp转换成复制成2n的连续石堆，找长度为n的石堆合并
  2. #include <iostream>
  3. #include <cstring>
  5. using namespace std;
  7. const int N = 410;
  9. int w[N],s[N];
  10. int f[N][N],g[N][N];
  12. int main(){
  13.     int n;
  14.     cin >> n;
  15.     //输入w[i]
  16.     for (int i = 1; i <= n; ++i) {
  17.         cin >> w[i];
  18.         w[i+n] = w[i];
  19.     }
  20.     //初始化
  21.     memset(f,0x3f,sizeof f);
  22.     memset(g,-0x3f,sizeof g);
  23.     //求前缀和
  24.     for (int i = 1; i <= 2 * n; ++i) s[i] = s[i-1] + w[i];
  25.     //dp
  26.     for (int len = 1; len <= n; ++len) 
  27.         for (int l = 1; len + l - 1 <= 2 * n; ++l) {
  28.             //r
  29.             int r = len + l - 1;
  30.             if (len == 1) f[l][r] = g[l][r] = 0;
  31.             else {
  32.                 for (int k = 1; k < r; ++k) {
  33.                     f[l][r] = min(f[l][r],f[l][k]+f[k+1][r] + s[r] - s[l-1]);
  34.                     g[l][r] = max(g[l][r],g[l][k]+g[k+1][r] + s[r] - s[l-1]);
  35.                 }
  36.             }
  37.         }
  38.     int minv = 0x3f3f3f3f, maxv = -0x3f3f3f3f;
  39.     for (int i = 1; i <= n; ++i) {
  40.         minv = min(minv,f[i][i+n-1]);
  41.         maxv = max(maxv,g[i][i+n-1]);
  42.     }
  43.     cout << minv << endl << maxv << endl;
  44.     return 0;
  45. }