【题目描述】

在一个圆形操场的四周摆放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;
}