专栏文章

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

封封禁用户
P11793题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mioalffu
此快照首次捕获于
2025/12/02 16:04
3 个月前
此快照最后确认于
2025/12/02 16:04
3 个月前
查看原文

题目分析

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

解题思路

使用动态规划（DP）求解： 设 dp[i]dp[i] 表示装好前 ii 个橙子的最小总成本。对于每个 ii（1≤i≤n1 \le i \le n），枚举最后一个箱子的起始位置 jj（jj 满足 i−m≤j<ii - m \le j < i），最后一个箱子装橙子 [j+1,i][j+1, i]。转移方程为：
dp[i]=min⁡j=max⁡(0,i−m)i−1(dp[j]+cost(j+1,i))dp[i] = \min_{j=\max(0, i-m)}^{i-1} \left( dp[j] + \text{cost}(j+1, i) \right)
其中 cost(j+1,i)=k+(i−j)×(max⁡t=j+1iAt−min⁡t=j+1iAt)\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]=0dp[0] = 0（没有橙子时成本为 0）。
  • 边界处理：当 j<0j < 0 时跳过。
在实现时，内层循环从 i−1i-1 反向枚举到 i−mi-m，同时动态维护区间 [j+1,i][j+1, i] 的最小值和最大值。

代码实现

CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...