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

P1775 石子合并（弱化版）

article 2025/2/1 8:54:34

P1775 石子合并（弱化版）

题目描述

设有 $\le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots,N$ 。每堆石子有一定的质量 $m_i\ (m_i \le 1000)$ 。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数 $N$ 。

第二行， $N$ 个整数 $m_i$ 。

输出格式

输出文件仅一个整数，也就是最小代价。

样例 #1

样例输入 #1

4
2 5 3 1

样例输出 #1

题解分析

这道题目可以通过区间动态规划来解决。我们的目标是将多个石子堆合并成一堆，而每次合并相邻的两堆所需要的代价是这两堆石子质量之和。因为每次合并顺序不同，总的合并代价也会不同，所以我们要找到一种顺序，使得总的合并代价最小。

动态规划状态定义

我们设 dp[i][j] 表示将第 i 堆到第 j 堆的石子合并成一堆的最小代价。这个问题的关键是，如何从已经合并好的子区间合并出更大的区间。

状态转移

初始状态：
- 对于任何单独的一堆石子，即 dp[i][i]，合并代价为 0，因为它已经是一个单独的堆，不需要合并。
状态转移方程：
对于区间 [i, j]，我们可以选择一个中间点 k 来分割区间 [i, j]，使得左半部分是 [i, k]，右半部分是 [k+1, j]，然后将这两个子区间的结果合并。合并这两个子区间的代价为这两个子区间的质量和。

因此，dp[i][j] 可以通过以下方式计算：
$\min(dp[i][k] + dp[k+1][j] + \text{sum}[i, j]) \quad \text{其中} \quad k \in [i, j-1]$
其中，sum[i, j] 表示从 i 到 j 的石子质量之和。
如何计算区间的质量和？
使用前缀和来快速计算任意区间 [i, j] 的石子质量和。前缀和数组 sum[i] 记录了从第 1 堆到第 i 堆的质量之和。通过前缀和，我们可以在常数时间内得到任意区间 [i, j] 的和：
$\text{sum}[i, j] = \text{sum}[j] - \text{sum}[i-1]$

算法复杂度

时间复杂度：
- 我们需要填充一个 dp 数组，其中有 O(N^2) 个状态。
- 对于每一个 dp[i][j]，我们需要枚举中间点 k，这使得每个状态的转移需要 O(N) 的时间。
- 因此，总的时间复杂度是 O(N^3)，其中 N 最大为 300，这使得该算法在给定输入限制下是可行的。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

#define int long long
using namespace std;

const int N = 300 + 10;
const int INF = 1e18;

int dp[N][N];    // dp[i][j] 存储合并区间 [i, j] 的最小代价
int sum[N];      // sum[i] 存储从 1 到 i 的前缀和

void solve() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    
    // 输入石子的质量
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    // 计算前缀和
    sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + v[i];
    }

    // 初始化 dp 数组
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = 0;  // 单个堆合并代价为0
    }

    // 动态规划计算
    for (int len = 2; len <= n; ++len) {  // len 表示区间长度
        for (int l = 1; l <= n - len + 1; ++l) {  // l 表示区间左端点
            int r = l + len - 1;  // r 表示区间右端点
            dp[l][r] = INF;  // 初始化为无穷大
            for (int k = l; k < r; ++k) {  // k 为中间点，分割区间
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    }

    // 输出最小代价
    cout << dp[1][n] << endl;
}

signed main() {
    solve();
    return 0;
}

代码分析

输入和前缀和的计算：
- 我们先读取石子的质量，并计算出前缀和数组 sum[]，这样可以快速计算任何区间 [i, j] 的石子质量和。
初始化动态规划数组：
- 对于每个区间 [i, i]，即单独一堆石子，合并代价为 0，因此 dp[i][i] = 0。
动态规划过程：
- 我们使用三重循环来计算所有区间的最小代价：
  - 外层循环遍历区间的长度 len。
  - 中层循环遍历区间的左端点 l。
  - 内层循环遍历中间点 k，将区间 [l, r] 分为 [l, k] 和 [k+1, r] 两个子区间，计算合并代价。
最小代价输出：
- 最终，dp[1][n] 即为将所有石子堆合并成一堆的最小代价。