当前位置：首页 > article >正文

[NOI1995] 石子合并

article 2025/1/30 11:39:42

[NOI1995] 石子合并

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

$1\leq N\leq 100$ ， $0\leq a_i\leq 20$ 。

题目大意

在一个圆形操场的四周摆放了 $N$ 堆石子。每次操作中，你只能选择相邻的两堆石子进行合并，并且合并的得分是这两堆石子的数量之和。最终的目标是将所有石子合并为一堆，要求你计算出合并过程中得到的最小得分和最大得分。

解题思路

这道题目涉及到动态规划（Dynamic Programming, DP）和圆形排列的处理。我们可以将圆形的石子排列“展平”成一条线，并使用动态规划解决合并过程中的最小得分和最大得分问题。具体步骤如下：

展平圆形结构：由于石子的排列是圆形的，我们可以通过将数组复制一遍并拼接起来，变成一个长度为 $2 N$ 的数组。这样，我们就可以将圆形结构当作一个线性结构来处理。
动态规划状态定义：
- dp1[l][r]：表示在区间 $[l, r]$ 内合并所有石子的最小得分。
- dp2[l][r]：表示在区间 $[l, r]$ 内合并所有石子的最大得分。
状态转移方程：
- 计算最小得分时，我们可以选择区间内的任意一个位置进行合并，更新dp1[l][r]：
  [
  dp1[l][r] = \min(dp1[l][r], dp1[l][k] + dp1[k+1][r] + sum[r] - sum[l-1])
  ]
- 同样地，计算最大得分时更新dp2[l][r]：
  [
  dp2[l][r] = \max(dp2[l][r], dp2[l][k] + dp2[k+1][r] + sum[r] - sum[l-1])
  ]
前缀和的计算：为了更快速地计算区间和，我们可以使用一个sum数组，其中sum[i]表示从第一个石子到第 $i$ 个石子的总和。
最终结果：由于是一个环形结构，我们需要对dp1和dp2中所有可能的区间（长度为 $N$ 的子区间）计算最小值和最大值。

代码分析

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 1e9 + 7;
const int N = 300 + 10;

int n;
int dp1[N][N];  // 最小得分 DP
int dp2[N][N];  // 最大得分 DP
int sum[N];     // 前缀和数组
vector<int> v(N);  // 石子的数量

void clear() {
    for (int i = 0; i < N; ++i) {
        for (int j = i; j < N; ++j) {
            if (i == j) {
                dp1[i][j] = 0;
                dp2[i][j] = 0;
            } else {
                dp1[i][j] = inf;
                dp2[i][j] = -inf;
            }
        }
    }
}

void solved() {
    clear();
    
    cin >> n;  // 读入石子的堆数
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        sum[i] = sum[i - 1] + v[i];  // 计算前缀和
    }

    // 扩展石子数组，处理圆形结构
    for (int i = n + 1; i <= 2 * n; ++i) {
        v[i] = v[i - n];
        sum[i] = sum[i - 1] + v[i];
    }

    // 计算 dp 数组
    for (int len = 2; len <= n; ++len) {  // 长度从2到n
        for (int l = 1; l <= 2 * n - len + 1; ++l) {  // 枚举区间起始位置
            int r = l + len - 1;  // 区间的右端
            for (int k = l; k < r; ++k) {  // 枚举分割点
                dp1[l][r] = min(dp1[l][r], dp1[l][k] + dp1[k + 1][r] + sum[r] - sum[l - 1]);
                dp2[l][r] = max(dp2[l][r], dp2[l][k] + dp2[k + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    }

    int minn = inf, maxx = -inf;
    for (int l = 1; l <= n; ++l) {  // 最终结果遍历所有可能的起始位置
        minn = min(minn, dp1[l][l + n - 1]);
        maxx = max(maxx, dp2[l][l + n - 1]);
    }

    cout << minn << endl;  // 输出最小得分
    cout << maxx << endl;  // 输出最大得分
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) {
        solved();
    }
}

代码分析

初始化和前缀和：首先初始化 dp1 和 dp2 数组，dp1[i][j] 用于保存区间 $[i, j]$ 的最小合并得分，dp2[i][j] 用于保存区间 $[i, j]$ 的最大合并得分。我们也通过 sum 数组计算了从第一个石子到第 $i$ 个石子的前缀和。
展开圆形数组：由于问题中石子是圆形排列的，我们通过将数组从头到尾复制一次，形成一个长度为 $2 N$ 的新数组 v，并且更新对应的前缀和 sum。
动态规划计算：通过枚举区间长度 len 和起始位置 l，以及每个区间内的分割点 k，使用状态转移方程更新 dp1 和 dp2 数组。最终，通过遍历所有可能的区间，找到最小得分和最大得分。
时间复杂度：由于有三重循环（区间长度、区间起点、分割点），时间复杂度为 $O(N^3)$ 。对于 $\leq 100$ ，这种复杂度是可以接受的。