推荐这篇题解：http://www.cnblogs.com/Blacko/archive/2013/10/18/3376597.html
只不过这篇题解有一些细节没有说清，但建议自己思考～
Codes:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1010,M=10010;
int D[N];
ll up[N],leave[N],upt[N];ll sum[N],f[N];struct Passenger{
int s,e;
ll t;
}p[M];ll endt[N];int n,m,k;
inline ll conc(bool spdup){
int nt,np;
nt=np=0;
ll eff=-0x7fffffff,idx=-1,ne;
//计算endt
for(int i=1;i<=n;i++){ endt[i]=max(endt[i-1],upt[i-1])+D[i-1]; } //计算f for(int i=n-1;i>=1;i--)f[i]=(upt[i+1]>=endt[i+1]?1:f[i+1]+1);
//计算eff
for(int i=1;i<=n;i++){ if(!D[i])continue; ne=sum[f[i]+i]-sum[i]; if(ne>eff)eff=ne,idx=i;
}
if(spdup)D[idx]--;
else{
nt=0;
for(int i=1;i<=m;i++)
nt+=endt[p[i].e]-p[i].t;
return nt;
}
return 0;
}int main(){
#ifdef LOCAL
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n-1;i++){
scanf("%d",&D[i]);
}
ll t,u,l;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&t,&u,&l);
upt[u]=max(upt[u],t);
up[u]++;
leave[l]++;
p[i].s=u,p[i].e=l,p[i].t=t;
}
//计算sum
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+leave[i];
for(int i=1;i<=k;i++){
conc(true);
}
printf("%lld\n",conc(false));
return 0;
} |
Solution:
两点需要注意的地方（按上方题解提供的数组含义来写）：
1.f[i]的推导。我一开始以为是若last[i+1]>time[i+1]则为0，得到的结果比答案大一点点……然后稍微魔改成了last[i+1]>=time[i+1]则为1,就tm对了……想了一下，可能是因为即使下一个站需要等待，这一个站至少能影响到第二个站；以及为什么是last[i+1]>=time[i+1]而非last[i+1]>time[i+1]——当last[i+1]==time[i+1]时，此时time[i+1]再减少，下一个站仍然会变成需要等待，所以也对后方没有影响，所以last[i+1]>=time[i+1]才是正确的范围。
2.当一条边已经被加速到0时，不能再加速。
其它看上面的题解和我的代码吧2333