saymyname's blog

topcoder SRM 591 DIV2 1000 point DP problem..
By saymyname, 11 years ago, In English

Hi, could any one explain the DP approach of this problem. http://community.topcoder.com/stat?c=problem_statement&pm=12750&rd=15703 I tried to solve using topdown approach but I was unable to implement. I want to discuss on both the approaches. Also please suggest some links to practice on similar problems.

Thanks in Advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

Very straight forward DP problem.

First you need to calculate dp[S]: How many ways to form a team which has sum S.

When you are calculating the dp array, you need to choose the ith player who has skill[i] in decreasing order, when the conditions hold:

J > sumSkillsOfAllPlayers - J
and
J - skill[i] < sumSkillsOfAllPlayers - (J - skill[i])

you can add dp[ J - skill[i] ] to your answer.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you please provide me some link which covers most of the straight forward dp problems..

    → Reply