往返委托 题解

设委托总数为 $K=m+l$。

题意整理

每份委托都有确定的出发地点、开始时刻、到达地点和到达时刻：

• 出发委托 $(a,x)$：从物流中心出发，开始时刻为 $x$，在 $x+t_a$ 到达服务站 $a$；
• 返回委托 $(b,y)$：从服务站 $b$ 出发，开始时刻为 $y$，在 $y+t_b$ 到达物流中心。

在某一时刻到达后，可以立刻接受同一时刻从当前位置开始的委托。因此，可衔接的条件是“上一份委托的到达时刻不晚于下一份委托的开始时刻”，等号必须允许。

最后一份委托不要求回到物流中心，所以答案要统计以任意一类委托结尾的方案。

部分分做法

子任务 1：状态搜索

当 $K\le 18$ 时，可以记忆化搜索状态

$$(S,p,z),$$

其中 $S$ 是已经接受的委托集合，$p$ 是当前位置，$z$ 是当前时刻。枚举一份尚未使用、出发地点为 $p$ 且开始时刻不早于 $z$ 的委托进行转移。

时间复杂度为 $O(2^K K)$，可以获得 $10$ 分。

子任务 2：委托 DAG

把每份委托看作一个点。如果委托 $u$ 的到达地点是委托 $v$ 的出发地点，且 $u$ 的到达时刻不晚于 $v$ 的开始时刻，就从 $u$ 向 $v$ 连边。

因为 $t_i\ge 1$，一份委托的到达时刻严格晚于自己的开始时刻，按开始时刻排序后，这是一张 DAG。令 $dp_v$ 表示以 $v$ 结尾最多接受多少份委托，枚举所有前驱转移即可。

时间复杂度为 $O(K^2)$，空间复杂度为 $O(K)$，可以通过前两个子任务，获得 $35$ 分。

子任务 3：只有一个服务站

此时只有“物流中心”和“服务站 $1$”两个位置。按时间扫描委托，并分别维护当前已经到达两个位置的最优答案即可。到达事件必须排在同一时刻的委托开始事件之前。

这个做法只需维护两个位置的状态，是完整事件 DP 的直接过渡，可以获得该子任务的 $15$ 分。

子任务 4：每个服务站至多一份返回委托

考虑服务站 $i$ 唯一的返回委托 $(i,y)$。若要用它完成一次往返，应选择一份满足 $x+t_i\le y$ 的出发委托 $(i,x)$。在这些出发委托中选择开始时刻最大的一个一定不劣：它更容易接在之前的路线后面，而返回物流中心的时刻仍然都是 $y+t_i$。

这样，每份返回委托至多产生一个候选往返区间

$$[x,\ y+t_i],$$

完成一个区间恰好接受两份委托。按结束时刻排序，使用经典的最早结束贪心，就能选择最多的互不冲突往返区间。所有完整往返结束后，如果存在开始时刻不早于当前时刻的出发委托，还可以再接受一份作为最后一份委托。

用排序和二分找到每份返回委托对应的最晚出发委托，总时间复杂度为 $O(K\log K)$，可以获得该子任务的 $20$ 分。

正解：离线事件 DP

直接建立 $O(K^2)$ 条委托之间的边没有必要。下一份委托能否接受，只取决于：在它开始以前，能够到达其出发地点的方案中，最多已经接受了多少份委托。

维护：

• $center$：已经到达物流中心的方案中，接受委托数的最大值；
• $station_i$：已经到达服务站 $i$ 的方案中，接受委托数的最大值。

初始时调度员在物流中心，所以 $center=0$；所有 $station_i$ 都不可达。

对每份委托建立两个事件。

1. 开始事件：在委托规定的时刻尝试接受它，并计算以它结尾的 DP 值。
2. 到达事件：在开始时刻加上对应的 $t_i$ 后，用这份委托的 DP 值更新到达地点。

具体地：

• 出发委托的开始事件令 $dp=center+1$，其到达事件用 $dp$ 更新 $station_a$；
• 返回委托只有在 $station_b$ 可达时才能接受，开始事件令 $dp=station_b+1$，其到达事件用 $dp$ 更新 $center$。

将全部 $2K$ 个事件按时间排序。时间相同时，必须先处理到达事件，再处理开始事件，才能正确表示“到达后立即接单”。

同一时刻可能有多份开始事件。它们虽然会读取相同的地点状态，但开始事件本身只写入对应委托的 $dp$，直到至少 $t_i\ge 1$ 个时间单位之后的到达事件才更新地点状态，所以同一时刻的委托不会互相错误转移，也自然满足同一时刻至多接受一份。

每次成功计算一份委托的 $dp$ 时都更新答案。不能只输出 $center$，否则会错误地强制最后一份委托必须返回物流中心。

正确性证明

引理 1

处理时刻 $z$ 的所有开始事件前，$center$ 和每个 $station_i$ 分别等于所有不晚于时刻 $z$ 到达对应地点的可行方案中，接受委托数的最大值。

证明：所有到达时刻小于 $z$ 的到达事件已经被处理；同一时刻的到达事件也因排序规则先于开始事件处理。每个到达事件都用产生它的可行方案更新正确的目的地，因此所有已经到达的方案都被纳入。到达时刻晚于 $z$ 的事件尚未处理，不会被提前使用。故命题成立。

引理 2

每份委托开始事件算出的 $dp$，等于所有以该委托为最后一份委托的可行方案中，接受委托数的最大值。

证明：若它是出发委托，根据引理 1，$center$ 恰好给出开始时刻前已到达物流中心的最优可行前缀；接上本委托得到 $center+1$。若它是返回委托，同理应从对应的 $station_i$ 转移；该状态不可达时委托也不可接受。任意以本委托结尾的方案，其前缀都必须在开始时刻前到达规定地点，因此不会优于上述转移。故命题成立。

引理 3

算法不会在同一时刻连续接受两份委托。

证明：开始事件只计算委托的 $dp$，不会立即更新任何地点状态。由于 $t_i\ge 1$，该委托对应的到达事件严格晚于开始事件。因此，同一时刻的另一份委托不能使用刚计算出的 $dp$。故命题成立。

定理

算法输出的答案等于最多能够接受的委托数量。

证明：由引理 2，每个成功计算的 $dp$ 都对应一个真实可行方案，故答案不会偏大。任意最优方案都有一份最后接受的委托；由引理 2，这份委托的 $dp$ 至少为该方案长度，且算法会用它更新答案，故答案不会偏小。两者结合，算法正确。

复杂度分析

共有 $2K$ 个事件。排序的时间复杂度为 $O(K\log K)$，扫描为 $O(K)$；存储事件、委托和各地点状态的空间复杂度为 $O(n+K)$。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

namespace {

constexpr int NEGATIVE_INFINITY = -1000000000;

struct Job {
    int station = 0;
    bool is_departure = false;
    int best = NEGATIVE_INFINITY;
};

struct Event {
    std::int64_t time = 0;
    int kind = 0;
    int job_id = 0;

    bool operator<(const Event& other) const {
        if (time != other.time) {
            return time < other.time;
        }
        return kind < other.kind;
    }
};

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int m = 0;
    int l = 0;
    std::cin >> n >> m >> l;

    std::vector<std::int64_t> travel_time(n + 1);
    for (int station = 1; station <= n; ++station) {
        std::cin >> travel_time[station];
    }

    const int job_count = m + l;
    std::vector<Job> jobs(job_count);
    std::vector<Event> events;
    events.reserve(2 * job_count);

    for (int job_id = 0; job_id < job_count; ++job_id) {
        int station = 0;
        std::int64_t start_time = 0;
        std::cin >> station >> start_time;
        const bool is_departure = job_id < m;
        jobs[job_id].station = station;
        jobs[job_id].is_departure = is_departure;

        events.push_back({start_time, 1, job_id});
        events.push_back({start_time + travel_time[station], 0, job_id});
    }

    std::sort(events.begin(), events.end());

    int center_best = 0;
    std::vector<int> station_best(n + 1, NEGATIVE_INFINITY);
    int answer = 0;

    for (const Event& event : events) {
        Job& job = jobs[event.job_id];
        if (event.kind == 0) {
            if (job.best == NEGATIVE_INFINITY) {
                continue;
            }
            if (job.is_departure) {
                station_best[job.station] = std::max(station_best[job.station], job.best);
            } else {
                center_best = std::max(center_best, job.best);
            }
        } else if (job.is_departure) {
            job.best = center_best + 1;
            answer = std::max(answer, job.best);
        } else if (station_best[job.station] != NEGATIVE_INFINITY) {
            job.best = station_best[job.station] + 1;
            answer = std::max(answer, job.best);
        }
    }

    std::cout << answer << '\n';
    return 0;
}