Hi Friends !
I have been trying this problem from a long time but could not solve this till now.
So , Please help me.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 153 |
5 | maroonrk | 153 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
9 | orz | 145 |
10 | pajenegod | 144 |
Hi Friends !
I have been trying this problem from a long time but could not solve this till now.
So , Please help me.
Название |
---|
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!