题目描述:
某城市的地铁只有一条线路, 有n个车站(n<=50), 有M1辆列车从1号站往右开, M2辆列车从n号站往左开
间谍Mario从1号站出发, 要在时刻T(T<=200)会见在n站的一个间谍, 给出地铁的发车时刻和相邻两个站之间的行驶时间, 求Mario在车站上的最少等待时间(无解输出”impossible”)
思路:
以时间为序的多阶段dp
设d(i,j)是间谍Mario在车站i, 时刻j的最小等待时间
则答案为d(n,T), 初始化d(0,0)=0, 其它d为无穷大, 若d(n,T)等于无穷大无解
状态转移方程见代码:
代码:
1 |
|