短且简 。
贪心 是基本思想。
其他操作主要体现在 前缀 来优化上。

这里推荐一个博主的写法，先看为敬。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct SEGMENT {
    int l, r, v, maxv, p;
};
int N, M, K, Ans;
// Arr是到达时间， Sat是出发时间
int Arr[1005], Sat[1005], Out[1005], Man[1005], D[1005];
int main () {
    
    ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    for(int i=1; i<N; i++) cin >> D[i];
    for(int i=1, t, a, b; i<=M; i++) {
        cin >> t >> a >> b;
        // 先减去每个人 "上车前的时间" ，后面直接用 "到达时间*到达人数" 整体计算消耗时间，从而优化程序 
        Ans-=t;
        Out[b]++;
        Sat[a]=max(Sat[a], t);
    }
    while(K--) {        
        memset(Man, 0, sizeof(Man));    
        for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1]; 
        // 从 "后缀" 开始寻找当前路径上正在运输的人数
        for(int i=N; i>1; i--) {
            if (D[i-1]) {
                Man[i-1]=Out[i];
                if (Arr[i]>Sat[i]) Man[i-1]+=Man[i];    
            } 
            else Man[i-1]=0;
        }
        int maxm=0, p=0;
        for(int i=1; i<=N; i++) 
            if (Man[i]>maxm) {
                maxm=Man[i];
                p=i;      
            }
        if (!p) break;
        D[p]--;    
    }
    for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1];
    for(int i=1; i<=N; i++) Ans+=Arr[i]*Out[i];
    cout << Ans;
    return 0;
    
}

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
const int M=10010;
int d[N],getto[N],getoff[N],latest[N], f[N];
struct Passenger{
    int t,s,e;
}a[M];

inline int read()
{
    char ch=getchar();
    int x=0;
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}

int main()
{
    int n,m,k;
    n=read();
    m=read();
    k=read();
    for(int i=1; i<n; i ++)
        d[i] = read();
    for(int i=1; i<=m; i ++){
        a[i].t=read();
        a[i].s=read();
        a[i].e=read();
        latest[a[i].s]=max(latest[a[i].s], a[i].t);
        getoff[a[i].e]++;
    }
    for(int i=1; i<=n; i ++)
        getto[i]=max(getto[i-1],latest[i-1])+d[i-1];
    while(k--){
        for(int i=n; i>=2; i--){
            if(!d[i-1])
                f[i-1]=0;
            else{
                f[i-1]=getoff[i];
                if(getto[i]>latest[i])
                    f[i-1]=f[i-1]+f[i];
            }
        }
        int maxtime=0, pos=0;
        for (int i=1; i<n; i ++)
            if (f[i]>maxtime){
                maxtime=f[i];
                pos=i;
            }
        if(pos==0)
            break;
        d[pos]--;
        for(int i=pos+1; i<=n; i++)
            getto[i]=max(getto[i-1],latest[i-1])+d[i-1];
    }
    int tot=0;
    for(int i=1; i<=m; i++)
        tot+=getto[a[i].e]-a[i].t;
    cout<<tot;
    return 0;
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,m,k,ans=0;
int D[1005],T[10005],qi[10005],zhong[10005];
int late[1005],ari[1005],sum[1005],maxn[1005];
int up[1005],down[1005];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<n;i++) 
       scanf("%d",&D[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&T[i],&qi[i],&zhong[i]);
        maxn[qi[i]]=max(maxn[qi[i]],T[i]);//人最晚到达某个景点的时间 ； 
        up[qi[i]]++;//上车的人数 ； 
        down[zhong[i]]++;//下车的人数； 
    }
    for(int i=1;i<=n;i++){
        ari[i]=late[i-1]+D[i-1];//车到达每个景点的时间； 
        late[i]=max(ari[i],maxn[i]);//最后一个到达这个景点的时间 
        sum[i]=down[i+1];//要下车的人数； 
    }
    for(int i=1;i<=m;i++)
        ans+=(ari[zhong[i]]-T[i]);//不使用加速器花费的总时间； 
    for(int i=n-2;i>=1;i--)
        if(ari[i+1]>maxn[i+1]) 
          sum[i]+=sum[i+1];//找最大的 人等车的区间的 下车的人数； 
    while(k>0){
        int x=0;
        for(int i=1;i<n;i++)
            if(sum[i]>sum[x]&&D[i]>0) 
              x=i;//找下车人数最多的区间，（加速的效果最好） 
        if(x==0) break;
            D[x]--;//两个景点间的时间——； 
            k--;//加速装置的个数——； 
            ans-=sum[x];//减去节省的时间；（有几个要下车人就节省几分钟）； 
        for(int j=x;j<=n;j++){
            ari[j]=late[j-1]+D[j-1];
            late[j]=max(ari[j],maxn[j]);
            sum[j]=down[j+1];
        }
        for(int j=n-2;j>=x;j--)
            if(ari[j+1]>maxn[j+1]) 
              sum[j]+=sum[j+1];//用完一个加速装置后重新统计区间； 
    }
    printf("%d",ans);
    return 0; 
}

先把不加速的总时间算出来（有10分。。）
然后计算加速器的最大影响（影响加速的时间段和使所有乘客不用等待）

#include<stdio.h>
#include<stdlib.h>
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int i,d[1001]={0};
for(i=1;i<=n-1;i++) scanf("%d",&d[i]);
int t[10001],a[10001],b[10001];
int people[1001]={0},go[1001]={0},arrive[1001]={0};
//people[i]为在第i个站用1个加速器能造福的人数即1个加速器的效益；
//go[i]为第i站的出发时间；arrive[i]为第i站的到达时间；
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&t[i],&a[i],&b[i]);
people[b[i]-1]++;
go[a[i]]=max(go[a[i]],t[i]);
}
for(i=2;i<=n;i++)
arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];
int j;
while(k--)//每次循环找出这个加速器用在哪一站的效益最大；
{
int max1=0,c=0,T=0;
for(j=n;j>1;j--)//从后往前推，则直到不符合要求(第j站）的下一站（第j+1站）所得的效益才是在第j+1站用加速器得到的效益；(如果j和j+1都符合要求，则第j站的效益肯定大于第j+1站，所以要从后往前推）；
{
if(arrive[j]<=go[j]) c=0;//如果到达时间小于出发时间，用加速器也没有效益；
c+=people[j-1];//反之，记录下这个加速器的效益；
if(d[j-1]>0&&c>max1) max1=c,T=j-1;
}
if(T==0) break;
d[T]--;
for(i=T+1;i<=n;i++) arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];//每用一次加速器则更新所用加速器的那站之后的站的到达时间；
}
int sum=0;
for(i=1;i<=n;i++)

arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];//最后再更新一次，以免有漏更新的站；
for(i=1;i<=m;i++)
sum+=arrive[b[i]]-t[i];
printf("%d",sum);
fclose(stdin);
fclose(stdout);
return 0;
}

#include <cstdio>
#include <iostream>
using namespace std;
int dis[1003],Time[1003],tn[1003],Up[1003],Down[1003];
bool picked[1003];
int ans,n,m,k,kans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<n;i++) scanf("%d",dis+i);
for (int i=1,t,l,r;i<=m;i++)
{
scanf("%d%d%d",&t,&l,&r);
Up[l]++,Down[r]++;
Time[l]=max(t,Time[l]);
kans+=t;
}
for (int i=1;i<=n;i++)
tn[i]=max(tn[i-1],Time[i-1])+dis[i-1];
while (k--)
{
int M_cng=0,C_Cng=0,T=0;
for (int j=n;j>1;j--)
{
if (tn[j]<=Time[j]) C_Cng=0;
C_Cng+=Down[j];
if (dis[j-1] && C_Cng>M_cng) M_cng=C_Cng,T=j-1;
}
if (!T) break;
dis[T]--;
for (int i=T+1;i<=n;i++) tn[i]=max(tn[i-1],Time[i-1])+dis[i-1];
}
ans=0;
for (int i=1;i<=n;i++)
tn[i]=max(tn[i-1],Time[i-1])+dis[i-1],ans+=Down[i]*tn[i];
printf("%d\n",ans-kans);
return 0;
}

11年的题怎么都这么水。。。
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1000 + 10;
const int maxm = 10000 + 10;

int n, m, k;
int ans;
int D[maxn], wait[maxn], down[maxn];
int arrive[maxn], leave[maxn], sum[maxn];
int T[maxm], A[maxm], B[maxm];

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n >> m >> k;
for (int i = 1; i < n; i++) cin >> D[i];
for (int i = 0; i < m; i++) {
cin >> T[i] >> A[i] >> B[i];
wait[A[i]] = max(wait[A[i]], T[i]);
down[B[i]]++;
}

for (int i = 1; i <= n; i++) {
arrive[i] = leave[i-1] + D[i-1];
leave[i] = max(arrive[i], wait[i]);
sum[i] = down[i+1];
}

for (int i = 0; i < m; i++)
ans += arrive[B[i]] - T[i];

for (int i = n-2; i >= 1; i--)
if (arrive[i+1] > wait[i+1]) sum[i] += sum[i+1];

while (k) {
int cur = 0;
for (int i = 1; i < n; i++)
if (sum[i] > sum[cur] && D[i]) cur = i;

if (!cur) break;
D[cur]--; k--;
ans -= sum[cur];

for (int i = cur; i <= n; i++) {
arrive[i] = leave[i-1] + D[i-1];
leave[i] = max(arrive[i], wait[i]);
sum[i] = down[i+1];
}

for (int i = n-2; i >= cur; i--)
if (arrive[i+1] > wait[i+1]) sum[i] += sum[i+1];
}
cout << ans;
return 0;
}
```

http://www.ofsxb.com/archives/128
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,m,k;
int D[1000+10],T[10000+10],A[10000+10],B[10000+10];

int ans=0;
int s[1000+10],t[1000+10],sum[1000+10],M[1000+10];
int up[1000+10],down[1000+10];

int dd[1000+10];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++) scanf("%d",&D[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d",&T[i],&A[i],&B[i]),M[A[i]]=max(M[A[i]],T[i]),up[A[i]]++,down[B[i]]++;

for(int i=1;i<=n;i++)
{
t[i]=s[i-1]+D[i-1];
s[i]=max(t[i],M[i]);
sum[i]=down[i+1];
}
for(int i=1;i<=m;i++)
ans+=(t[B[i]]-T[i]);

for(int i=n-2;i>=1;i--)
if(t[i+1]>M[i+1]) sum[i]+=sum[i+1];

while(k>0)
{
int x=0;
for(int i=1;i<n;i++)
if(sum[i]>sum[x]&&D[i]>0) x=i;

if(x==0) break;

D[x]--;
k--;
ans-=sum[x];

for(int j=x;j<=n;j++)
{
t[j]=s[j-1]+D[j-1];
s[j]=max(t[j],M[j]);
sum[j]=down[j+1];
}

for(int j=n-2;j>=x;j--)
if(t[j+1]>M[j+1]) sum[j]+=sum[j+1];
}
cout<<ans;

return 0;
}

/*

Author : Slience_K
Belong : C++
Pro : NOIP 2011 - 2 - 3

*/

#include <cstdio>
#include <algorithm>
using namespace std;
int n , m , k , d[ 1005 ];
int st[ 1005 ] , down[ 1005 ] , art[ 1005 ] , ans , sum[ 1005 ];
int main(){
scanf( "%d%d%d" , &n , &m , &k );
for( int i = 2 ; i <= n ; i++ )
scanf( "%d" , &d[ i ] );
ans = 0;
for( int i = 1 , a , b , c ; i <= m ; i++ ){
scanf( "%d%d%d" , &a , &b , &c );
down[ c ]++;
ans -= a;
st[ b ] = max( st[ b ] , a );
}
for( int i = 2 ; i <= n ; i++ )
art[ i ] = max( art[ i - 1 ] , st[ i - 1 ] ) + d[ i ];
for( int l = 1 ; l <= k ; l++ ){
for( int i = n ; i >= 2 ; i-- ){
sum[ i ] = down[ i ];
if ( art[ i ] > st[ i ] ) sum[ i ] += sum[ i + 1 ];
}
int maxn = 0 , pos = 0;
for( int i = 2 ; i <= n ; i++ )
if (( maxn < sum[ i ] )&&( d[ i ] >= 1 )){
maxn = sum[ i ];
pos = i;
}
if ( !pos ) break;
d[ pos ] -= 1;
for( int i = pos ; i <= n ; i++ )
art[ i ] = max( st[ i - 1 ] , art[ i - 1 ] ) + d[ i ];
}
for( int i = 1 ; i <= n ; i++ )
ans += down[ i ] * art[ i ];
printf( "%d" , ans );
return 0;
}

NOIP2014赛前AC留念
（如此捉鸡的贪心我也是醉了……）
var ans,n,m,k,i:longint;
arrive,d,t,a,b,down,latest:array[0..10001] of longint;

function mmax(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

procedure doit;
var i,j,max,tip,pos:longint;
begin
pos:=0;
max:=0;
for i:=1 to n-1 do
if d[i]>0 then
begin
tip:=0;
for j:=i+1 to n do
begin
tip:=tip+down[j];
if arrive[j]<=latest[j] then break;
end;

if tip>max then
begin
max:=tip;
pos:=i;
end;
end;
dec(d[pos]);
for i:=2 to n do
arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
dec(k);
end;

begin
//assign(input,'t6.in');
//assign(output,'t6.out');
//reset(input);
//rewrite(output);
readln(n,m,k);
for i:=1 to n-1 do read(d[i]);
for i:=1 to m do
begin
readln(t[i],a[i],b[i]);
if latest[a[i]]<t[i] then latest[a[i]]:=t[i];
inc(down[b[i]]);
end;
arrive[1]:=latest[1];
for i:=2 to n do
arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
while k>0 do doit;

for i:=2 to n do
arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
ans:=0;
for i:=1 to m do
ans:=ans+arrive[b[i]]-t[i];
writeln(ans);
//close(input);
//close(output);
end.

var
n,m,k,i,j,a,b,c,cct,ans,max1:longint;
time,last,d,data,num:array[0..2000] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
begin
readln(n,m,k);
for i:=2 to n do read(d[i]);
for i:=1 to m do
begin
readln(a,b,c);
ans:=ans-a;
inc(num[c]);
last[b]:=max(last[b],a);
end;
for i:=2 to n do time[i]:=max(time[i-1],last[i-1])+d[i];
for i:=1 to k do
begin
for j:=n downto 2 do
begin
data[j]:=num[j];
if last[j]<time[j] then data[j]:=data[j]+data[j+1];
end;
max1:=0;
for j:=2 to n do
if (data[j]>max1) and (d[j]>0) then
begin
max1:=data[j];
cct:=j;
end;
dec(d[cct]);
for j:=cct to n do
time[j]:=max(time[j-1],last[j-1])+d[j];
end;
for i:=2 to n do
ans:=ans+num[i]*time[i];
writeln(ans);
end.

VijosNT Mini 2.0.5.7 Special for Vijos

编译通过...

├ 测试数据 01：答案正确... (0ms, 676KB)

├ 测试数据 02：答案正确... (0ms, 676KB)

├ 测试数据 03：答案正确... (0ms, 676KB)

├ 测试数据 04：答案正确... (0ms, 676KB)

├ 测试数据 05：答案正确... (0ms, 676KB)

├ 测试数据 06：答案正确... (0ms, 676KB)

├ 测试数据 07：答案正确... (0ms, 676KB)

├ 测试数据 08：答案正确... (0ms, 676KB)

├ 测试数据 09：答案正确... (0ms, 676KB)

├ 测试数据 10：答案正确... (0ms, 676KB)

├ 测试数据 11：答案正确... (0ms, 676KB)

├ 测试数据 12：答案正确... (0ms, 676KB)

├ 测试数据 13：答案正确... (0ms, 676KB)

├ 测试数据 14：答案正确... (0ms, 676KB)

├ 测试数据 15：答案正确... (0ms, 676KB)

├ 测试数据 16：答案正确... (0ms, 676KB)

├ 测试数据 17：答案正确... (0ms, 676KB)

├ 测试数据 18：答案正确... (0ms, 676KB)

├ 测试数据 19：答案正确... (0ms, 676KB)

├ 测试数据 20：答案正确... (32ms, 676KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 32ms / 676KB

var

n,m,k,tt,ans,i,j,t:longint;

a,b:array[1..10000]of longint;

sum,time,late,d,f:array[1..1000]of longint;

function max(x,y:longint):longint;

begin

if xlate[a[i]] then late[a[i]]:=t;

for j:=b[i] to n do inc(sum[j]);

end;

end;

procedure main;

var i,ma,ii:longint;

begin

while k>0 do

begin

dec(k);

for i:=2 to n do time[i]:=max(time,late)+d;

f[n]:=n;

for i:=n-1 downto 1 do

if time0)and(ma

要认真审题啊！！！！
只需每次查找某点从一个此点到后某点间的下车人数最大， 且保证在这两点间车到达每点的时间大于该点最后一个人上车的时间

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,D[1005]={0},last[1005]={0},down[1005]={0},s[1005]={0},sum[1005]={0};
int T[10005],A[10005],B[10005],ari[1005]={0};
int main(){
//freopen("bus.in","r",stdin);
int i,t,a,b,ans=0;
scanf("%d %d %d",&n,&m,&k);
for(i=1;i<n;i++) scanf("%d",&D[i]);
for(i=1;i<=m;i++){
scanf("%d %d %d",&t,&a,&b);
T[i]=t;A[i]=a;B[i]=b;
last[a]=max(last[a],t);
down[b]++;
}
for(i=1;i<=n;i++){
ari[i]=s[i-1]+D[i-1];
s[i]=max(ari[i],last[i]);
sum[i]=down[i+1];
}
for(i=1;i<=m;i++){
ans+=ari[B[i]]-T[i];
}
for(i=n-2;i>=1;i--){
if(ari[i+1]>last[i+1])
sum[i]+=sum[i+1];
}
while(k){
int x=0;
for(i=1;i<=n-1;i++)
if(sum[i]>sum[x]&&D[i]>0) x=i;
if(x==0) break;
D[x]--;
ans-=sum[x];
k--;
for(i=x;i<=n;i++){
ari[i]=s[i-1]+D[i-1];
s[i]=max(ari[i],last[i]);
sum[i]=down[i+1];
}
for(i=n-2;i>=x;i--){
if(ari[i+1]>last[i+1])
sum[i]+=sum[i+1];
}
}
printf("%d\n",ans);
return 0;
}