crazy_cow's blog

Need Help in DP Problem

By crazy_cow, 12 years ago, In English

Hi Friends !

I have been trying this problem from a long time but could not solve this till now.

So , Please help me.

http://www.spoj.com/problems/MPILOT/

Tags dp, spoj
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
12 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I dont know how you have been trying , but i just solved it with greedy .

As the input is sorted with age , I imagined it like a string with '(' and ')' where '(' is assistant and ')' is captain . now i need it to be a valid bracket sequence with least cost .

For each character i will try to place ')' and add cost_captain to answer and save (cost_assistant — cost_captain ) in a multiset/priority_queue . when placing ')' violates rule , then get the minimum value from the multiset & add it to the answer . This means I have reversed a previous ')' to '(' that have least cost .

almost similar problem : http://mirror.codeforces.com/contest/3/problem/D

→ Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

solution that moinul.shaon mentioned is ok but if you still need the dp solution then here it is:

A[i] is salary for pilot i if he was an assistant

B[i] is salary for pilot i if he was a captain

dp[i][j] means the least cost after assigning pilots from 1 to i and you have j assistants who are not yet having captains in their planes ( of course j <= i ) when you compute dp[i][j] you have two situations that lead to it , either you had j + 1 assistants and you made the i'th pilot a captain then he took one of the assistants available, or you had j - 1 assistants and you made the i'th pilot an assistant so he will be added to the j - 1 assistants so the formula of dp is:

dp[i][j] = min(dp[i - 1][j + 1] + B[i], dp[i - 1][j - 1] + A[i])

→ Reply