Sammmmmmm's blog

By Sammmmmmm, history, 15 months ago, In English

Hi can someone help me with this problem? Thanks

Link: https://oj.uz/problem/view/JOI18_candies

For every k where 1 <= k <= n / 2, find out what's the maximum total value you can achieved by choosing k elements from an array of n integers, and no 2 consecutive elements are chosen.

N <= 2e5;

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

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Have you found the solution? Can you explain it to me?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Hint: Try solving it with weighted maximum matching, and optimize it further.