北京网站建设公司哪个最好,鲜花网页设计模板,网站分几个阶段建设,获取网站缩略图的asp代码P1315 [NOIP2011 提高组] 观光公交 我们想在 \(k\) 次加速每一次都取当前最优的方案加速。 考虑怎样计算对于每一条边如果在当前情况下使用加速器能够使答案减少的大小。 如果当前到达某个点时已经有人在等待了#xff0c;那么加速这个点以前的边能够让这个点下车的人距离减少… P1315 [NOIP2011 提高组] 观光公交 我们想在 \(k\) 次加速每一次都取当前最优的方案加速。 考虑怎样计算对于每一条边如果在当前情况下使用加速器能够使答案减少的大小。 如果当前到达某个点时已经有人在等待了那么加速这个点以前的边能够让这个点下车的人距离减少而对于仍旧在车上的没有贡献。 如果到达这个点时车还需要等待人那么加速之前的的边对车上人的影响会在以后的点(直至这些人下车时)再会计算而能够让在这个点下车的人距离减少。 综上我们发现减少一条边的距离会使在这个点下车的人距离减少这个贡献保留到人等车的那一刻所以我们就可以在 \(k\) 次加速每次处理到达这个点的时间与最后一个人到达的时间到这取最大值即可。 #define Maxn 10005
int n,m,k,ans;
int Last[Maxn],cntup[Maxn],cntdown[Maxn],arr[Maxn],d[Maxn];
int s[Maxn],t[Maxn],x[Maxn];
int main()
{nrd(),mrd(),krd();for(int i2;in;i) d[i]rd();for(int i1;im;i){x[i]rd(),s[i]rd(),t[i]rd();cntup[s[i]],cntdown[t[i]];Last[s[i]]max(Last[s[i]],x[i]);ans-x[i];}while(k--){for(int i1;in;i)arr[i]max(Last[i],arr[i-1]d[i]);int hav0,MAX0,pos0;for(int in;i2;i--){if(arr[i]Last[i]) havcntdown[i];else{havcntdown[i];if(d[i] havMAX) MAXhav,posi;}}if(pos) d[pos]--;else break;}for(int i1;in;i)arr[i]max(Last[i],arr[i-1]d[i]),anscntdown[i]*(arr[i-1]d[i]);printf(%d\n,ans);return 0;
}
