TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1329
  • 题目
  • P1329【NOIP 2011 DAY2-3】观光公交
    限制 : 时间限制 : 20000 MS   空间限制 : 128000 KB
    问题描述

    风景迷人的小城 Y 市,拥有n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第0 分钟出现在1号景点,随后依次前往2、3、4……n 号景点。从第i 号景点开到第i+1 号景点需要Di 分钟。
    任意时刻,公交车只能往前开,或在景点处等待。
    设共有 m 个游客,每位游客需要乘车1 次从一个景点到达另一个景点,第i 位游客在Ti 分钟来到景点Ai,希望乘车前往景点Bi(Ai假设乘客上下车不需要时间。
    一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ 给公交车安装了k 个氮气加速器,每使用一个加速器,可以使其中一个Di 减1。对于同一个Di 可以重复使用加速器,但是必须保证使用后Di 大于等于0。
    那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

    输入格式

    第 1 行是3 个整数n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
    第 2 行是n-1 个整数,每两个整数之间用一个空格隔开,第i 个数表示从第i 个景点开往第i+1 个景点所需要的时间,即Di。
    第 3 行至m+2 行每行3 个整数Ti, Ai, Bi,每两个整数之间用一个空格隔开。第i+2 行表示第i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

    输出格式

    共一行,包含一个整数,表示最小的总旅行时间。

    样例输入

    3 3 2
    1 4
    0 1 3
    1 1 2
    5 2 3

    样例输出

    10

    提示

    数据范围】
    对于 10%的数据,k=0;
    对于 20%的数据,k=1;
    对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500;
    对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000;
    对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000,0 ≤ k ≤ 100,000,0 ≤ Di ≤ 100,
    0 ≤ Ti ≤ 100,000。

    【输入输出样例说明】
    对 D2 使用2 个加速器,从2 号景点到3 号景点时间变为2 分钟。
    公交车在第 1 分钟从1 号景点出发,第2 分钟到达2 号景点,第5 分钟从2 号景点出发,第7 分钟到达3 号景点。
    第 1 个旅客旅行时间 7-0 = 7 分钟。
    第 2 个旅客旅行时间 2-1 = 1 分钟。
    第 3 个旅客旅行时间 7-5 = 2 分钟。
    总时间 7+1+2 = 10 分钟。


    来源  NOIP 2011 高中组 第二天 第3题