题解

本题使用动态规划求解分段装箱的最小代价问题。

算法思路：

1. 状态定义：

   • dp[i]：将前 $i$ 个橙子装箱的最小代价
   • 每个箱子最多装 $m$ 个橙子
   • 每个箱子的代价为 $k + (max - min) \times 箱子内橙子数$

2. 转移方程：

   • 枚举最后一个箱子的起始位置 $j$（满足 $i - j + 1 \leq m$）
   • 计算区间 $[j, i]$ 的最大值 $mx$ 和最小值 $mn$
   • 转移：$dp[i] = \min(dp[i], dp[j-1] + k + (mx - mn) \times (i - j + 1))$

3. 优化策略：

   • 在转移时同时维护区间 $[j, i]$ 的最大值和最小值
   • 从 $i$ 向前枚举 $j$，动态更新 $mn$ 和 $mx$
   • 只需要枚举最近的 $m$ 个位置

4. 边界条件：

   • $dp[0] = 0$（没有橙子时代价为 $0$）
   • 初始化 $dp[i] = \infty$

5. 答案输出：

   • 输出 $dp[n]$

时间复杂度：$O(n \times m)$，对于每个位置 $i$，最多枚举 $m$ 个起始位置。

这是一道经典的分段DP问题，关键在于理解状态转移和代价的计算方式。

#include <iostream>
#define MAXN 20003
#define IMX 0x3f3f3f3f
#define LMX 0x3f3f3f3f3f3f3f3fLL
using namespace std;
using lli = long long;

int a[MAXN];
lli dp[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1, mn, mx; i <= n; ++i)
    {
        cin >> a[i], mn = IMX, mx = -IMX, dp[i] = LMX;
        for (int j = i; j && i - j < m; --j)
        {
            mn = min(mn, a[j]), mx = max(mx, a[j]);
            dp[i] = min(dp[i], k + (lli)(mx - mn) * (i - j + 1) + dp[j - 1]);
        }
    }
    cout << dp[n];
    return 0;
}