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.net/contest/3/problem/D

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])