「POI2014 R3」装货 Freight 题解

题目分析

我们有 $n$ 列火车，每列火车在时间 $t_i$ 到达上字节镇站。火车需要：

1. 从上字节镇站发车到下字节镇站（耗时 $s$ 分钟）
2. 在下字节镇站装货（时间忽略）
3. 从下字节镇站返回上字节镇站（耗时 $s$ 分钟）

约束条件：

• 发车间隔至少 1 分钟
• 铁轨是单轨，所有火车必须同向行驶
• 求最后一列火车返回上字节镇站的最早时间

关键观察

1. 火车分组策略

由于铁轨是单轨且火车必须同向行驶，最优策略是将火车分成若干批次：

• 同一批次的火车可以连续发车（间隔 1 分钟）
• 不同批次的火车之间需要等待前一批完全返回

2. 时间计算

对于第 $i$ 列火车：

• 如果它单独发车：返回时间 = $t_i + 2s$
• 如果它和前面的火车一起发车：需要考虑发车间隔和等待时间

动态规划解法

状态定义

设 $dp[i]$ 表示前 $i$ 列火车全部返回上字节镇站的最早时间。

状态转移

考虑第 $i$ 列火车所在的批次：

• 如果第 $i$ 列火车单独发车：$dp[i] = \max(dp[i-1], t_i) + 2s$
• 如果第 $i$ 列火车和前面的 $k$ 列火车一起发车： 这批火车的最晚到达时间：$t_i$ 这批火车的发车时间：$\max(dp[j], t_i)$（其中 $j$ 是前一批的最后一列） 这批火车的返回时间：$\max(dp[j], t_i) + 2s + (i-j)$

更精确的转移方程：

$$dp[i] = \min_{0 \leq j < i} \left\{ \max(dp[j] + (i-j), t_i) + 2s + (i-j-1) \right\} $$

其中：

• $j$ 是前一批的最后一列火车索引
• $i-j$ 是当前批次的火车数量
• $\max(dp[j] + (i-j), t_i)$ 是当前批次第一列火车的发车时间
• $2s$ 是往返时间
• $(i-j-1)$ 是批次内其他火车的额外等待时间

优化解法

通过观察可以发现，最优解具有单调性，可以使用贪心策略：

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

typedef long long ll;
const int MAXN = 1e6 + 5;

int n, s;
ll t[MAXN];
ll dp[MAXN];

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &t[i]);
    }
    
    // 确保到达时间单调不降
    for (int i = 2; i <= n; i++) {
        t[i] = max(t[i], t[i-1]);
    }
    
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        // 尝试将火车分组
        for (int j = 0; j < i; j++) {
            // j+1 到 i 作为一批
            ll start_time = max(dp[j] + (i - j), t[i]);
            dp[i] = min(dp[i], start_time + 2 * s + (i - j - 1));
        }
    }
    
    printf("%lld\n", dp[n]);
    return 0;
}

更高效的解法

对于大数据范围 ($n \leq 10^6$)，需要 $O(n)$ 或 $O(n \log n)$ 的算法。

观察发现，最优分组具有决策单调性，可以使用单调队列优化：

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

typedef long long ll;
const int MAXN = 1e6 + 5;

int n, s;
ll t[MAXN];
ll dp[MAXN];

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &t[i]);
        t[i] = max(t[i], t[i-1]);  // 确保单调性
    }
    
    dp[0] = 0;
    int ptr = 0;  // 最优决策指针
    
    for (int i = 1; i <= n; i++) {
        // 移动指针找到最优决策
        while (ptr + 1 < i && 
               max(dp[ptr] + (i - ptr), t[i]) + 2 * s + (i - ptr - 1) >= 
               max(dp[ptr+1] + (i - ptr - 1), t[i]) + 2 * s + (i - ptr - 2)) {
            ptr++;
        }
        
        dp[i] = max(dp[ptr] + (i - ptr), t[i]) + 2 * s + (i - ptr - 1);
    }
    
    printf("%lld\n", dp[n]);
    return 0;
}

样例分析

样例输入：

3 4
1 8 11

计算过程：

• 火车到达时间：1, 8, 11
• 单程时间：s = 4

最优分组：三列火车分成两个批次

• 第一批：火车1（单独）
  • 发车时间：max(0, 1) = 1
  • 返回时间：1 + 4 + 4 = 9
• 第二批：火车2和火车3
  • 发车时间：max(9 + 2, 11) = 11
  • 火车2返回：11 + 4 + 4 = 19
  • 火车3返回：11 + 4 + 4 + 1 = 20

最终答案：20

算法正确性证明

1. 最优子结构：前 $i$ 列火车的最优解可以由前 $j$ 列的最优解推导得出
2. 决策单调性：随着 $i$ 增大，最优的 $j$ 也会单调不减
3. 边界处理：正确处理第一列火车和最后一列火车的情况

复杂度分析

• 直接DP：$O(n^2)$，适用于 $n \leq 5000$
• 单调队列优化：$O(n)$，适用于 $n \leq 10^6$
• 空间复杂度：$O(n)$

总结

这道题的关键在于理解火车分组的最优策略和利用决策单调性进行优化。通过将问题转化为动态规划，并使用单调队列优化，可以在 $O(n)$ 时间内求解大规模数据。