描述
风景迷人的小城Y市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后依次前往2、3、4……n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。
设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai<Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。
一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机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位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。
输出格式
共一行，包含一个整数，表示最小的总旅行时间。
样例1
样例输入1
3 3 2 1 4 0 1 3 1 1 2 5 2 3
样例输出1
10
限制
1s
提示
样例说明：
对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分钟。
数据范围：
对于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。
题解
贪心。因为所有人到达站点的时间是不变的，所以车什么时候离开站点，取决于最晚到该站的人的到达时间。那么只有那些“车到达时间>最晚到该站的人的到达时间”的路段需要被优化，显然对于这样一段的道路，在这段中的第一条路上加速到尽量快是最优的。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 1002
#define MAXM 10002
using namespace std;
int n,m,K,d[MAXN];
struct ren{int t,a,b;} r[MAXM];
int arv[MAXN],sum[MAXN],last[MAXN];
int nx[MAXN],ans,tot;
//------------------------------------------------------------
void init()
{
scanf("%d%d%d",&n,&m,&K);
int i;
for(i=1;i<n;i++) scanf("%d",&d[i]);
for(i=1;i<=m;i++)
{scanf("%d%d%d",&r[i].t,&r[i].a,&r[i].b);
last[r[i].a]=max(last[r[i].a],r[i].t);
sum[r[i].b]++;
}
for(i=2;i<=n;i++)
{arv[i]=max(arv[i-1],last[i-1])+d[i-1];
sum[i]+=sum[i-1];
}
nx[n]=n; nx[n-1]=n;
for(i=n-2;i>=1;i--)
{if(arv[i+1]>last[i+1]) nx[i]=nx[i+1];
else nx[i]=i+1;
}
for(i=1;i<=m;i++) ans+=arv[r[i].b]-r[i].t;
}
void work()
{
int i,maxs=0,l,r;
for(i=1;i<=n-1;i++)
{if(maxs<sum[nx[i]]-sum[i]&&d[i]>0)
{maxs=sum[nx[i]]-sum[i]; l=i; r=nx[i];}
}
tot+=maxs;
d[l]--;
if(r==n) r=n-1;
for(i=l+1;i<=r;i++) arv[i]=max(arv[i-1],last[i-1])+d[i-1];
for(i=r;i>=l;i--)
{if(arv[i+1]>last[i+1]) nx[i]=nx[i+1];
else nx[i]=i+1;
}
}
int main()
{
init();
while(K--) work();
printf("%d\n",ans-tot);
return 0;
}