[NOI1995] 石子合并

[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\le N\le 100$，$0\le a_i\le 20$。

题目大意

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

解题思路

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

1. 展平圆形结构：由于石子的排列是圆形的，我们可以通过将数组复制一遍并拼接起来，变成一个长度为 $2N$ 的数组。这样，我们就可以将圆形结构当作一个线性结构来处理。

2. 动态规划状态定义：

   • dp1[l][r]：表示在区间 $[l,r]$ 内合并所有石子的最小得分。
   • dp2[l][r]：表示在区间 $[l,r]$ 内合并所有石子的最大得分。

3. 状态转移方程：

   • 计算最小得分时，我们可以选择区间内的任意一个位置进行合并，更新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])
     ]

4. 前缀和的计算：为了更快速地计算区间和，我们可以使用一个sum数组，其中sum[i]表示从第一个石子到第 $i$ 个石子的总和。

5. 最终结果：由于是一个环形结构，我们需要对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到nfor (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();}
}

代码分析

1. 初始化和前缀和：首先初始化 dp1 和 dp2 数组，dp1[i][j] 用于保存区间 $[i,j]$ 的最小合并得分，dp2[i][j] 用于保存区间 $[i,j]$ 的最大合并得分。我们也通过 sum 数组计算了从第一个石子到第 $i$ 个石子的前缀和。

2. 展开圆形数组：由于问题中石子是圆形排列的，我们通过将数组从头到尾复制一次，形成一个长度为 $2N$ 的新数组 v，并且更新对应的前缀和 sum。

3. 动态规划计算：通过枚举区间长度 len 和起始位置 l，以及每个区间内的分割点 k，使用状态转移方程更新 dp1 和 dp2 数组。最终，通过遍历所有可能的区间，找到最小得分和最大得分。

4. 时间复杂度：由于有三重循环（区间长度、区间起点、分割点），时间复杂度为 $O(N^3)$。对于 $N\le 100$，这种复杂度是可以接受的。

总结

这个问题的核心在于如何利用动态规划求解合并石子的最小和最大得分。通过将圆形结构展开为线性结构，可以简化问题的求解。算法通过动态规划计算每个区间的最小和最大得分，并最终遍历所有可能的区间来求解答案。