「POI2009 R2」列车长 Ticket Inspector 题解

题目大意

Bajtazar 在列车上担任列车长，他需要在整条线路上进行 $k$ 次查票。已知所有乘客的行程信息：$x_{i,j}$ 表示从站 $i$ 上车、在站 $j$ 下车的乘客数。

关键规则：

• 查票发生在离开某个站点之后
• 乘客只在第一次被查到时计入工资
• 要选择 $k$ 个查票位置，使得查到的不重复乘客数最多

算法思路

核心观察

对于一个从站 $a$ 上车、站 $b$ 下车的乘客：

• 他会在区间 $[a, b-1]$ 的任何查票中被查到
• 但只计入第一次被查到的那个查票点

动态规划解法

设 $dp[i][t]$ 表示在位置 $i$ 进行第 $t$ 次查票时的最大收益。

状态转移： [ dp[i][t] = \max_{0 \le j < i} \left( dp[j][t-1] + gain(j, i) \right) ]

其中 $gain(j, i)$ 表示当上一次查票在位置 $j$，这次在位置 $i$ 时新增的乘客数。

gain(j, i) 的计算

$gain(j, i)$ 包含所有满足以下条件的乘客 $(a,b)$：

• $j < a \le i < b$（在位置 $i$ 查票时乘客在车上，且之前没被查过）

高效计算方法：

1. 预处理 $cnt[a][i] = \sum_{b=i+1}^n x_{a,b}$（从站 $a$ 上车且在 $i$ 之后下车的乘客数）
2. 使用递推：$gain(j,i) = gain(j,i-1) + cnt[i][i] - \sum_{a=j+1}^{i-1} x_{a,i}$

复杂度分析

• 预处理：$O(n^2)$
• DP 状态数：$O(n \cdot k)$
• 总复杂度：$O(n^2 \cdot k)$，对于 $n \le 600, k \le 50$ 可接受

示例分析

对于样例输入：

7 2
2 1 8 2 1 0
3 5 1 0 1
3 1 2 2
3 5 6
3 2
1

程序输出：2 5

解释：

• 在位置 2 查票：能查到从站 1、2 上车的部分乘客
• 在位置 5 查票：能查到之前没被查过的乘客
• 这种选择方案使得查到的不重复乘客数最大化

总结

本题的关键在于：

1. 理解"乘客只计入第一次被查"的规则
2. 设计正确的 DP 状态和转移方程
3. 高效预处理 gain 数组
4. 通过记录前驱状态输出具体方案

使用动态规划结合巧妙的预处理，可以在合理时间内解决这个问题。