「APIO2024」星际列车 题解

问题概述

我们需要在$N$个行星之间通过$M$种星际列车路线旅行，从行星$0$到达行星$N-1$，同时满足$W$顿饭的用餐需求。目标是最小化车票价格和餐费的总和。

关键观察

1. 列车换乘约束：乘坐的列车序列必须满足终点站与下一趟起点站相同，且到达时间不晚于出发时间
2. 用餐成本差异：
   • 在列车上用餐：免费（时间区间$[A[i], B[i]]$内）
   • 在行星上用餐：每顿饭花费$T[i]$元
3. 用餐时间灵活：第$i$顿饭可以在$[L[i], R[i]]$内的任何时刻吃，没有顺序要求

算法思路

核心思想

使用动态规划结合凸包优化来高效计算最小花费。

状态设计

• 定义$dp[i][j]$为到达行星$i$在时间$vc[i][j]$的最小总花费
• 定义$dp2[i][j]$为到达行星$i$在时间$vc[i][j]$的最小车票花费（不含餐费）

其中$vc[i]$存储了所有与行星$i$相关的时间点（列车出发或到达时间）。

预处理

1. 时间点收集：收集所有行星的列车出发和到达时间
2. 用餐区间处理：使用持久化线段树统计在特定时间区间内的用餐次数
3. 时间排序：对所有相关时间进行排序和去重

动态规划转移

按时间顺序处理每个事件（行星在特定时间点）：

1. 用餐成本计算：对于当前行星$i$和时间点$j$，计算在$vc[i][j]$之后用餐的最小餐费
2. 列车转移：从当前状态转移到所有可能的下一趟列车

优化技巧

• 凸包优化：使用单调栈维护最优决策点，避免重复计算
• 持久化线段树：快速查询在任意时间区间内的用餐次数
• 时间离散化：将大范围时间映射到紧凑的索引

复杂度分析

• 时间：$O((N + M + W) \log W)$
• 空间：$O(N + M + W)$

实现细节

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

const long long inf = 1e17;

// 数据结构定义
struct Event { long long a, b; };
struct Train { long long a, b, c; };

// 持久化线段树用于统计用餐区间
struct PersistentSegTree {
    // 实现细节...
};

long long solve(int N, int M, int W, vector<int> T,
                vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C,
                vector<int> L, vector<int> R) {
    
    // 初始化数据结构
    vector<vector<long long>> time_points(N + 1);
    vector<vector<vector<Train>>> trains(N + 1);
    
    // 收集所有时间点
    vector<Event> events;
    
    // 处理用餐区间
    vector<int> gl, gr;
    // ... 实现用餐区间预处理
    
    // 动态规划数组初始化
    vector<vector<long long>> dp(N + 1), dp2(N + 1);
    
    // 主算法流程
    // 1. 按时间顺序处理事件
    // 2. 对于每个事件，更新用餐成本
    // 3. 进行列车转移
    // 4. 维护凸包优化结构
    
    // 返回结果
    long long result = min(dp[N].back(), dp2[N].back());
    return result == inf ? -1 : result;
}

样例分析

样例1

• 直接乘坐第2次列车花费$40$，在列车上免费用餐
• 优于换乘方案的花费$45$

样例2

• 乘坐第0次列车，车费$38$
• 合理安排在不同行星用餐：$33 \times 3 + 30 \times 2 = 197$
• 总花费$38 + 197 = 235$

总结

本题通过将复杂的时空约束转化为图上的动态规划问题，并利用数据结构优化餐费计算，实现了高效的最优解求解。关键在于正确处理用餐时间的灵活性和列车换乘的时序约束。