题解：P11793 [JOI 2016 Final] 橙子装箱 / Oranges

· · 题解

题目分析

有 n 个橙子排成一排，每个橙子的大小为 A_i。需要将它们装进若干个箱子里，每个箱子必须装连续的橙子，且最多装 m 个。每个箱子的成本为 k + (\text{箱子内橙子个数}) \times (\text{最大橙子大小} - \text{最小橙子大小})。目标是最小化总成本。

解题思路

使用动态规划（DP）求解： 设 dp[i] 表示装好前 i 个橙子的最小总成本。对于每个 i（1 \le i \le n），枚举最后一个箱子的起始位置 j（j 满足 i - m \le j < i），最后一个箱子装橙子 [j+1, i]。转移方程为：

dp[i] = \min_{j=\max(0, i-m)}^{i-1} \left( dp[j] + \text{cost}(j+1, i) \right)

其中 \text{cost}(j+1, i) = k + (i - j) \times (\max_{t=j+1}^{i} A_t - \min_{t=j+1}^{i} A_t)。

在实现时，内层循环从 i-1 反向枚举到 i-m，同时动态维护区间 [j+1, i] 的最小值和最大值。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    vector<long long> dp(n + 1, LLONG_MAX);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        int min_val = A[i];
        int max_val = A[i];
        for (int j = i - 1; j >= max(0, i - m); j--) {
            if (A[j + 1] < min_val) min_val = A[j + 1];
            if (A[j + 1] > max_val) max_val = A[j + 1];
            long long cost = k + 1LL * (i - j) * (max_val - min_val);
            if (dp[j] != LLONG_MAX) {
                if (dp[j] + cost < dp[i]) {
                    dp[i] = dp[j] + cost;
                }
            }
        }
    }

    cout << dp[n] << endl;
    return 0;
}