信息学奥赛一本通T1609-Cats Transport

原题来自：Codeforces Round #185 (Div. 1) B.

小 S 是农场主，他养了 M 只猫，雇了 P 位饲养员。农场中有一条笔直的路，路边有 N 座山，从 1 到 N 编号。第 i 座山与第 i−1 座山之间的距离是 D_i 。饲养员都住在 1 号山上。

有一天，猫出去玩。第 i 只猫去 Hi号山玩，玩到时刻 Ti 停止，然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从 1 号山走到 N 号山，把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间，速度为 1 米每单位时间。饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 1 的山，一只猫在 2 号山玩，玩到时刻 3 开始等待。如果饲养员从 1 号山在时刻 2 或 3 出发，那么他可以接到猫，猫的等待时间为 0 或 1。而如果他于时刻 1 出发，那么他将于时刻 2 经过 2 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1 号山出发的时间，使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。

第一行三个整数 N,M,P；

第二行 N−1 个正整数 D_i ，表示第 i 座山与第 i−1 座山之间的距离是 D_i ；

接下去 M 行每行两个整数 H_i,T_i 。

数据范围与提示：

对于全部数据，2≤N≤10⁵,1≤M≤10⁵,1≤p≤100,1≤D_i<10⁴,1≤H_i≤N,0≤T_i≤10⁹ 。

信息学一本通 动态规划