题目分析

有 $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)$。

• 初始状态：$dp[0] = 0$（没有橙子时成本为 0）。
• 边界处理：当 $j < 0$ 时跳过。

在实现时，内层循环从 $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;
}