题目描述

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。
输入格式
第一行包含整数 n，表示共有 n 堆石子。

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

输出格式
输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围
1≤n≤200

样例

输入样例：
4
4 5 9 4
输出样例：
43
54

算法1

(区间dp)

状态计算：
f[l][r] = min(f[l][r],f[l][k-1] + f[k][r] + a[r] - a[l - 1] )
g[l][r] = max(g[l][r],g[l][k-1] + g[k][r] + a[r] - a[l - 1] )

时间复杂度

O(2n^3)

参考文献

《算法提高课》

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 420, INF = 0x3f3f3f3f;

int f[N][N];
int g[N][N];
int a[N];

int main()
{
    int n;
    cin >> n;
    memset(f,INF,sizeof f);
    memset(g,-INF,sizeof g);

    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        a[i+n] = a[i];


    }
    for(int i = 1; i <= 2*n; i ++ )
    {
        a[i] += a[i-1];
        g[i][i] = 0;
        f[i][i] = 0;
    }    
    for(int len = 2 ; len <= n ;len ++ )
      for(int l = 1; l + len - 1 <= 2 * n ; l ++ )
      {
          int r = l + len - 1;
          for(int k = l - 1 ; k <= r; k ++ )
          {
              f[l][r] = min(f[l][r],f[l][k-1] + f[k][r] + a[r] - a[l - 1] );
              g[l][r] = max(g[l][r],g[l][k-1] + g[k][r] + a[r] - a[l - 1] );
          }
      }
       int minv = INF , maxv = -INF;
        for(int i = 1; i <= n;i++)
        {
            minv = min(minv, f[i][i + n - 1]);
            maxv = max(maxv, g[i][i + n - 1]);
        }
     cout << minv << endl << maxv << endl;

      return 0;
}