performance - 最高效率

Question

<分区>

Answer 1

看起来是动态的:

表示 a[ x ] - 从城市 x 收取的钱。

令 dp[ x ][ t ] 表示他花费时间 t 并在城市 x 完成可以获得的最大金额。初始化和更新如下:

1. 起点 x0，dp[ x0 ][ 0 ] := a[ x0 ]。对于其他城市 x dp[ x ][ 0 ] := -1 (无效);
2. 对于从1到T的每次t:
   每个城市 x:
   每个城市 y s.t. 边[y][x]<=t:
   表示 p := t - edge[ y ][ x ];
   if dp[ y ][ p ] >= 0//有可能在时间 p 到达 y
   然后 dp[ x ][ t ] = max( dp[ x ][ t ], dp[ y ][ t - edge[ x ][ y ]] + a[ x ] )
   
3. 返回所有 dp[ x ][ t ] 的最大值。

总复杂度为 O( T*N^2 )。