Hi Friends !
I have been trying this problem from a long time but could not solve this till now.
So , Please help me.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Hi Friends !
I have been trying this problem from a long time but could not solve this till now.
So , Please help me.
Name |
---|
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://codeforces.com/contest/3/problem/D
Thank You !
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])
Thank You!