首先推状态转移方程影响到决筞的只有当前的时间和所处的车站,可以用dp[i][j]表示时刻i间谍在车站j最少还需等待多长时间。如果达到目标即满足dp[T][n]有解那么考虑逆序递推,从终点开始考虑如何一步步状态转移到起点那么就是只有时间为T,当前车站为n的状态才能符合要求这里时间t是主要决策,故dp[T][n]设为0其他的dp[T][i]为inf
因为每趟车的出发时间给定且两个车站之间的路程时间给定,那么我们可以预处理每一辆车hsa_train[i][j][0\1]表示时刻i在车站j是否有向右/左开的車
然后每次都有三个状态去转移:
1.等待1分钟(1个时间单位)
dp[i][j]=dp[i+1][j]+1;即当前状态由前一个时间单位仍在j车站的状态得到
2.如果有则搭乘向右开的车
dp[i][j]=min(dp[i][j],dp[ i+t[j] ][j+1]);即当前状态是由前一个状态向左搭车得到的,因此后一个车站到左边的车站等同于左边的车站到后一个车站的时间t[j]
3.如果有则搭乘向左开嘚车