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

Help needed in this problem
Автор Madara__Uchiha__, история, 3 года назад, По-английски

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

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

»
3 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

It's pretty much Knapsack DP.

I will mention the dynamics:

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

$$$dp_{i,j,1}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ <=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

→ Ответить