Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage

Hints

If you want to solve this problem on your own without looking at the hints, solve 1132F : Clear the String first. Note that this recommendation is not for a similar problem or topic, but rather for a problem that will help you build your intuition and thought process. I’ve also added hints.

If you find the above problem too difficult, try 1901D: Yet Another Monster Fight. This will help you in thinking in the right direction instead of trying random things or greedy strategy. Hints are available

Recall that in Yet Another Monster Fight, instead of worrying above the original problem, we focused on what happens when the lightning strike starts at the i-th monsert. On similar lines, instead of solving the problem for the entire array, let’s solve it for the subarray that starts at i.

Formally, define dp[i] to be the maximum Cypriot value of the subarray starting at i (and ending at the last index). The answer to the original problem would then be dp[0].

How do you populate this DP?

You might try guessing how long the first cut would be, and then wondering how to compute the answer from the remaining dp[i], i.e. try the first cut (for the leftmost subarray) of length 1, 2, 3, … n and take the best out of them.

However, there’s a much simpler transition. Think about the technique used in Clear the String.

Instead of thinking about the first cut, think small. Think about what happens to the first element. Either it will be cut alone in a single subarray, or it’d be part of it’s neighbor’s cut. Can you figure out the DP transitions now?

If the i-th element is cut alone, it means that the first subarray is of size 1, adding a contribution of 1*a[i]. Now, we need to maximize 2*s1 + 3*s3 + ...

But we do know dp[i + 1] which is the maximum value for 1*s1 + 2*s2 + 3*s3 + ... . Hence, this diverts our attention on how these 2 equations are related:

E1 = 1*s1 + 2*s2 + 3*s3 ....
E2 = 2*s1 + 3*s3 + 4*s4 ....

It’s easy to see that

E2 - E1 = s1 + s2 + s3 + ....
E2 = E1 + sum[i + 1, ....]

Hence, if we want to maximize 2*s1 + 3*s3 + ..., then we should in fact maximize Cypriot value of dp[i + 1] and add the suffix sum.

Now, if the i-th element is not cut alone, then it is part of the first group. Hence, it would only contribute 1*a[i] while dp[i] will have the remaining contribution.

cut_with_group = a[i] + dp[i + 1]
cut_alone = a[i] + dp[i + 1] + suffix_sum[i + 1]

Hence, if we fill this DP array from right to left, we have an O(n) solution.

See the editorial for a discussion about Greedy vs DP.