Hello,
Can someone provide and explanation of the DP optimization used to get 100 points on Aliens of IOI 2016? I read their solution, but I still don't see how introducing the constant C helps you solve the problem. I also don't see the purpose of the g function they introduce.
Problem:https://ioinformatics.org/files/ioi2016problem6.pdf Solution: https://ioinformatics.org/files/ioi2016solutions.pdf
-dx24816
Here's an explanation for the same trick on a different problem: https://codeforces.com/blog/entry/49691
Another article: https://codeforces.com/blog/entry/68778