Блог пользователя saymyname

Автор saymyname, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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