城市里的间谍(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