题目理解

我们有一列火车，从站 $1$ 开到站 $n$，列车长 Bajtazar 要在途中进行 $k$ 次查票。
查票发生在离开某个站点之后，即在区间 $(i, i+1)$ 进行查票，我们把这个查票位置记为 $i$（$1 \le i \le n-1$）。

已知所有乘客的行程信息：$x_{i,j}$ 表示从站 $i$ 上车、在站 $j$ 下车的乘客数量。

关键规则：

• 如果在某段查票，会检查该段列车上所有乘客的票。
• 如果某个乘客在之前已经被查过票，那么再次查到时不计入工资。

目标：选择 $k$ 个查票位置，使得查到的不重复的乘客数最多。

---

思路分析

1. 乘客被查到的条件

假设一个乘客从 $a$ 上车，$b$ 下车（$a < b$）。
这个乘客会在离开站点 $a, a+1, \dots, b-1$ 之后的区间里都在车上。

如果我们在这 $b-a$ 个区间中的任何一个查票，都会查到这个乘客。
但只有第一次查到时才算工资。

因此，如果我们选择的查票位置中，该乘客行程覆盖的第一个查票位置是 $p$（$a \le p \le b-1$），那么该乘客的票会在位置 $p$ 被计入。

---

2. 问题转化

我们要选择 $k$ 个查票位置（$1 \dots n-1$ 中选 $k$ 个），最大化总收益。

收益计算方式：
对于每个乘客 $(a,b)$，如果我们在 $[a, b-1]$ 中选择了至少一个查票点，那么该乘客会被计入最小的那个查票点的贡献中。

---

3. 动态规划设计

设 $dp[i][t]$ 表示我们考虑了前 $i$ 个可能的查票位置（即 $1 \dots i$），并且在这里选择了 $t$ 次查票，所能获得的最大查票数。

转移方程： [ dp[i][t] = \max_{0 \le j < i} \left( dp[j][t-1] + gain(j, i) \right) ] 其中 $gain(j, i)$ 表示当上一次查票在位置 $j$（若 $j=0$ 表示还没查过票），这次查票在位置 $i$ 时，新增的乘客数量。

---

4. 计算 gain(j, i)

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

• $a \le i < b$ （在位置 $i$ 查票时乘客在车上）
• $j < a$ 或者 $b \le j+1$？
  我们需要仔细分析：乘客 $(a,b)$ 在位置 $i$ 被第一次查到，当且仅当：
  1. $a \le i < b$（在位置 $i$ 时乘客在车上）
  2. 在 $[a, i-1]$ 区间内没有查票（否则之前就查到了）

因为 $j$ 是上一次查票位置，那么 $[j+1, i-1]$ 之间没有查票。
所以如果 $a \le j$，那么乘客可能在 $j$ 或更早被查到过，不算在 $gain(j,i)$ 中。
因此条件为：$j < a \le i < b$。

也就是说，$gain(j,i)$ = 所有满足 $j < a \le i < b$ 的乘客 $(a,b)$ 的数量。

---

5. 预处理 gain 数组

我们可以预处理一个二维数组 $g[j][i]$ 表示 $gain(j,i)$。

注意 $j$ 从 $0$ 到 $n-1$，$i$ 从 $1$ 到 $n-1$，且 $j < i$。

计算方式：
固定 $j$，对于每个 $a$ ($j+1 \le a \le n-1$)，对于每个 $b$ ($a+1 \le b \le n$)，如果 $i \in [a, b-1]$，那么乘客 $(a,b)$ 会对 $g[j][i]$ 贡献 $x_{a,b}$。

我们可以用差分数组优化这个预处理，达到 $O(n^3)$ 预处理，但 $n \le 600$ 可能有点大。不过 $k \le 50$，也许可接受。

更高效的方法：
定义 $cnt[a][i]$ 表示从 $a$ 上车，在位置 $i$ 查票时能查到的乘客数（即 $b > i$ 的 $x_{a,b}$ 之和）。
那么： [ g[j][i] = \sum_{a = j+1}^{i} cnt[a][i] ] 其中 $cnt[a][i] = \sum_{b=i+1}^{n} x_{a,b}$。

我们可以 $O(n^2)$ 预处理 $cnt[a][i]$，然后 $O(n^3)$ 预处理 $g[j][i]$。
但 $600^3$ 太大（2.16e8），需要优化。

---

6. 优化 gain 计算

注意到： [ g[j][i] = g[j][i-1] + cnt[i][i] - \sum_{a=j+1}^{i-1} x_{a,i} ] 其中 $cnt[i][i] = \sum_{b=i+1}^n x_{i,b}$，而 $\sum_{a=j+1}^{i-1} x_{a,i}$ 表示那些从 $a$ ($j+1 \le a \le i-1$) 上车、在 $i$ 下车的乘客，他们在位置 $i$ 查票时已经下车了，所以不算。

这样我们可以在 $O(n^2)$ 时间内预处理 $g[j][i]$。

---

7. 动态规划实现

我们设 $dp[i][t]$ 表示前 $i$ 个位置选了 $t$ 次查票，且最后一次在 $i$ 查票的最大收益。
同时用 $pre[i][t]$ 记录前一个查票位置，用于输出方案。

转移： [ dp[i][t] = \max_{0 \le j < i} ( dp[j][t-1] + g[j][i] ) ] 初始 $dp[0][0] = 0$，其他 $-\infty$。

答案：$\max_{k \le i \le n-1} dp[i][k]$。

---

8. 输出方案

通过 $pre[i][t]$ 回溯，得到查票位置序列。

---

复杂度分析

• 预处理 $cnt$：$O(n^3)$（这里可以优化到 $O(n^2)$，通过后缀和）
• 预处理 $g$：$O(n^3)$（也可以优化到 $O(n^2)$）
• DP：$O(n^2 \cdot k)$

由于 $n \le 600, k \le 50$，$O(n^2 \cdot k)$ 约 $1.8 \times 10^7$ 可接受。

---

总结

这道题的核心在于：

1. 理解“乘客只在第一次被查时计入”这一规则
2. 将问题转化为动态规划模型
3. 高效预处理增益数组 $g[j][i]$
4. 通过记录前驱状态输出方案

这样就能在给定限制内求出最优查票方案。