【题目描述】

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

【输入描述】

数据的第 1 行是正整数 N，表示有 N 堆石子。

第 2 行有 N 个整数，第 i个整数ai表示第 i 堆石子的个数。

1≤N≤400，0≤ai≤20。

【输出描述】

输出共2行，第1 行为最小得分，第2 行为最大得分。

【样例输入】

4  4 5 9 4

【样例输出】

43  54

【题目分析】

1.输入处理：

使用静态数组 a 存储石子堆，并通过复制实现破环成链（a[i + N] = a[i]）。

前缀和数组 prefix 用于快速计算区间和。

2.DP 初始化：

dp_min[i][i] = 0 和 dp_max[i][i] = 0（合并单堆石子得分为 0）。

其他位置初始化为 INT_MAX（最小得分）和 INT_MIN（最大得分）。

3.区间 DP 计算：

三重循环：

外层循环枚举区间长度 len（从 2 到 N）。

中层循环枚举起点 i。

内层循环枚举分割点 k，更新 dp_min 和 dp_max。

区间和通过前缀和优化计算：sum = prefix[j + 1] - prefix[i]。

4.结果查询：

遍历所有可能的长度为 N 的区间，找到最小和最大得分。

破环成链：将环形问题转化为线性问题，避免复杂边界处理。

前缀和数组：将区间和计算从 O(N) 优化到 O(1)。

静态数组：避免动态内存分配，提高运行效率。

【参考答案】

#include <iostream>  #include <climits>  #include <algorithm>    using namespace std;    const int MAX_N = 410; // 最大石子堆数（稍大于 400）    int main() {      int N;      cin >> N;      int a[MAX_N * 2]; // 破环成链后的数组      int prefix[MAX_N * 2 + 1] = {0}; // 前缀和数组        // 输入石子堆      for (int i = 0; i < N; i++) {          cin >> a[i];          a[i + N] = a[i]; // 复制一份接在后面（破环成链）      }        // 计算前缀和      for (int i = 1; i <= 2 * N; i++) {          prefix[i] = prefix[i - 1] + a[i - 1];      }        // DP 数组      int dp_min[MAX_N * 2][MAX_N * 2];      int dp_max[MAX_N * 2][MAX_N * 2];        // 初始化 DP 数组      for (int i = 0; i < 2 * N; i++) {          for (int j = 0; j < 2 * N; j++) {              if (i == j) {                  dp_min[i][j] = 0; // 单堆石子合并得分为 0                  dp_max[i][j] = 0;              } else {                  dp_min[i][j] = INT_MAX; // 初始化为最大值                  dp_max[i][j] = INT_MIN; // 初始化为最小值              }          }      }        // 区间 DP      for (int len = 2; len <= N; len++) { // 枚举区间长度          for (int i = 0; i + len - 1 < 2 * N; i++) { // 枚举起点              int j = i + len - 1; // 区间终点              for (int k = i; k < j; k++) { // 枚举分割点                  // 当前区间的石子总数                  int sum = prefix[j + 1] - prefix[i];                  // 更新最小得分                  dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum);                  // 更新最大得分                  dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum);              }          }      }        // 在所有可能的长度为 N 的区间中找最小和最大得分      int min_score = INT_MAX;      int max_score = INT_MIN;      for (int i = 0; i < N; i++) {          min_score = min(min_score, dp_min[i][i + N - 1]);          max_score = max(max_score, dp_max[i][i + N - 1]);      }        cout << min_score << endl;      cout << max_score << endl;        return 0;  }