Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

jugal_sahu's blog

PILOTS spoj dp problem getting tle
By jugal_sahu, history, 11 years ago, In English

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

Tags dp
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

→ Reply