jhjfbsbfkbjfnfnfjfj's blog

By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

I could do this question by barely hit and trial like i first computed prefix sum then start taking terms which are at i-k position but i still couldn't understand thy dynamic programming concept behind it. please just explain this to me i will be very much thankful to you https://codeforces.net/contest/1253/problem/C

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See till count<=m it is clear, that we have to eat minimum possible sweet(s) that day. But after that, what we got to do is minimize the sum, which means that larger sweets(Ai) have to be consumed earlier. So for every count>m, we will eat the largest m sweets that day, but the remaining smaller ones next day, and the even smaller ones the day after. Now see that the ans array will have the prefix sum at each index, so when its day 2, we just need to add the minimum of remaining sweets(k-m) to the current sum, and that's why we are doing ans[i]+=ans[i-m]. Its best if you perform a simple check with pen and paper using the sample input. I am sure you will figure it out.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In this problem, it is always optimal to eat the m sweetest sweets first if you have to eat them so they do not get multiplied.

If i <= m, the answer is just the prefix sum because Yui can just eat all the candies on the first day.

sum(a, b) refers to the sum of the interval of a to b inclusive of candies in ascending order.

To find dp[i] if i > m, Yui has to do the following:

  1. Eat the m sweetest candies on the first day: sum(i-m+1, i)

  2. Eat the i-m candies left and increase that value by a factor of 1 because it would take Yui an additional day to eat these sweets: dp[i-m] + sum(1, i-m)

So the complete result is

sum(i-m+1, i) + dp[i-m] + sum(1, i-m)

=> dp[i-m] + sum(1, i)

=> dp[i-m] + (prefix sum up to i inclusive)

Hope this helps!