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

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

I was trying to solve this problem using top down dp but got tle.I read from comment that bottom up gives ac.But i am unable to implement bottom up dp.Please help.Thanks. Problem link: here My code link: here

Теги dp
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

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

Let DPi, j be the minimum cost of having i captains and j pilots. Let's number the pilots 1 to N, from youngest to oldest. If we are at a state (i, j), we're considering next pilot with index i + j + 1, and a state (i, j) is valid if i ≤ j (otherwise, we couldn't assign younger pilots to all the captains). From state (i, j), the valid transitions are to states (i, j + 1) and (i + 1, j).

Here's the code: C++ Code