城市里的间谍（A Spy in the Metro UVa 1025）最详细题解 - Monica - CSDN博客
这道题一看要问最少需要等待多少时间，自然会想到用dp，那么怎么来处理这个问题呢？我们可以用dp[i][j]来表示时刻i，你现在身处第j个站，最少还需要等待多长时间，我们所知的是，在T时刻，你人一定需要在第n个车站去完成间谍任务，所以dp[T][n]=0;可以由这个位置来进行反推，比如我在时刻T-1可以仍然位于车站n或者说如果有往左开的车我就有选择往左坐车的可能；
那么我们对于一个dp[i][j]进行状态转移，有三种转移方式：
Read full article from 城市里的间谍（A Spy in the Metro UVa 1025）最详细题解 - Monica - CSDN博客
No comments:
Post a Comment