7807: BZOJ3807:Neerc2011 Lanes

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

某座大桥上有n1条从左至右的车道,n2(n1,n2≤10) 条从右至左的车道,还有一条潮汐车道。 在早上从左向右行驶的车辆较多,潮汐车道的方向是 从左向右;晚上正好相反。 也就是说早上有n1+1条左右车道,n2条右左车道;晚 上有n1条左右车道,n2+1条右左车道。 交通是很复杂的问题,我们有如下的抽象模型: 从早到晚被分为m(m≤100000)个离散的时刻,编号从1开始。 在每个时刻,两侧均有一些车抵达。 设左右车道和右左车道各有L,R条车道,那么左侧通行L辆车 (即减少L辆车),右侧通行R辆车。 剩下的车等待下一时刻。 如果在时刻m后仍有车辆在等待,那么后面的时刻仍按同样模 型进行,只是不会有新到达的车辆了。 你的任务是决定在哪一时刻改变潮汐车道的方向,能 使所有车辆等待时间的总和最小化。 不过潮汐车道也不是瞬间就能改变方向的,它需要r 个时刻来改变方向。也就是说,如果在t时刻改变方向,那么在[t,t+r-1] 时刻内潮汐车道不能使用,即左右和右左车道各有n1和n2条。


输入格式


输出格式


样例输入

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

样例输出

4

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: