ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2110. Remove or Maximize

why always wa#10
Posted by abreto 18 Jan 2017 13:06
dp[n][k] = max{dp[n-1][k] or a[n], dp[n-1][k-1]}
any hints?? thank you.

Edited by author 18.01.2017 13:16
Re: why always wa#10
Posted by FlashKa 30 Aug 2018 16:03
3 2
7 6 1
Answer: 7

3 2
6 1 7
Answer: 7
Re: why always wa#10
Posted by Zergatul 7 Nov 2020 05:24
because DP like this doesn't work
lets consider next case
3 1
90 75 20

when we calculate last step we have:
dp[3][1] = max(dp[2][1] or 20, dp[2][0])
now dp[2][1] = 90, dp[2][0] = 90 or 75 = 91
we are choosing max between (90 or 20) and 91, which is equal to 94
but this is incorrect answer
correct answer is 75 or 20 = 95