1748: Cats Transport

题目描述


原题来自:Codeforces Round #185 (Div. 1) B.
小 S 是农场主,他养了
M
M 只猫,雇了
P
P 位饲养员。农场中有一条笔直的路,路边有
N
N 座山,从
1
1 到
N
N 编号。第
i
i 座山与第
i-1
i−1 座山之间的距离是
D_i
Di
。饲养员都住在
1
1 号山上。
有一天,猫出去玩。第
i
i 只猫去
H_i
Hi
号山玩,玩到时刻
T_i
Ti
停止,然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从
1
1 号山走到
N
N 号山,把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间,速度为
1
1 米每单位时间。饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。
例如有两座相距为
1
1 的山,一只猫在
2
2 号山玩,玩到时刻
3
3 开始等待。如果饲养员从
1
1 号山在时刻
2
2 或
3
3 出发,那么他可以接到猫,猫的等待时间为
0
0 或
1
1。而如果他于时刻
1
1出发,那么他将于时刻
2
2 经过
2
2 号山,不能接到当时仍在玩的猫。
你的任务是规划每个饲养员从
1
1 号山出发的时间,使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。

输入


第一行三个整数
N,M,P
N,M,P;
第二行
N-1
N−1 个正整数
D_i
Di
,表示第
i
i 座山与第
i-1
i−1 座山之间的距离是
D_i
Di

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

输出


输出一个整数表示答案。

样例输入


4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

样例输出


3

提示


数据范围与提示
对于全部数据,
2\le N\le 10^5,1\le M\le 10^5,1\le p\le 100,1\le D_i\lt 10^4,1\le H_i\le N,0\le T_i\le 10^9
2≤N≤105,1≤M≤105,1≤p≤100,1≤Di
<104,1≤Hi
≤N,0≤Ti
≤109。

来源/分类


ybttg DP 斜率优化

请先 登录 后评论
  • 0 关注
  • 0 收藏,419 浏览
  • 轩爸 提出于 2019-08-02 22:21

相似问题