Блог пользователя VAMPIER

Автор VAMPIER, история, 9 лет назад, По-английски

if there is anyone solve this problem please comment with the link of solution https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=698

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It can be solved with DP.

  • First of all, let's divide everything by 5 to make things simpler.
  • Let DP[i][t] be the maximum amount of fish we can catch if we start at lake i and have t minutes left. It's easier done with recursive DP with memoization, trying to stay as much as possible at each lake. To reconstruct the answer, along with the DP value, store the amount of time spent to achieve the best answer.
  • Finally, reconstruct the answer and remember to multiply values by 5.