Madara__Uchiha__'s blog

Help needed in this problem
By Madara__Uchiha__, history, 6 years ago, In English

Problem:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/the-chocolate-boy-738c799b/

My sub:- https://pastebin.com/E1hqm56H

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

Comments Comments (4)
| Write comment?
»
6 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

It's pretty much Knapsack DP.

I will mention the dynamics:

$$$dp_{i,j,0}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ \lt =j\ and\ operation\ is not\ used.$$$

$$$dp_{i,j,1}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ \lt =j\ and\ operation\ is\ used.$$$

$$$Transitions\ are\ similar\ to\ Knapsack\ DP.$$$

Your answer will be $$$max(dp[n][m][0]\ ,\ dp[n][m][1])$$$

My solution: https://ideone.com/NgqsT4

→ Reply