Given an array of $$$N$$$ $$$(1 \le N \le 10^5)$$$ elements $$$A_1,A_2,\dots,A_N$$$ $$$(1 \le A_i \le 10^6)$$$. You can replace $$$2$$$ consecutive elements with their sum. Find the minimum number of replacements such that the resulting array is non-decreasing.
As you can easily see, it is the same as split $$$A$$$ into maximum number of segments such that their sums from left to right is non-decreasing.
Thanks.
Words are not enough to describe the distress that this problem has caused me. I suffered more anxiety while trying this problem than I have felt in my entire life up to this point. I felt more depressed after each WA than I felt during some of the funerals of some people close to me. This problem has been very important in changing my perception of the world, as I now understand the true depths of despair.
profile photo checks out
I think this task is almost the same. My spoilers are for the linked problem.
You can come up with $$$DP[i][j]$$$ — the least possible sum of last segment, if the last segment is $$$j$$$ and it ends at a position $$$i$$$.
We can completely get rid of $$$j$$$ dimension, and store $$$DP[i]$$$ as a pair $$$(mx, sum)$$$. $$$mx$$$ is the maximum number of segments we can divide the prefix $$$(a_1, \ldots, a_i)$$$ into, and $$$sum$$$ is the least possible sum of last segment.
It's the same problem as https://oj.uz/problem/view/IZhO19_segments. Solution:https://codeforces.com/blog/entry/64479?#comment-484350
Also same as this problem from TCO Regionals of this year
Also same as this 2015 ICPC regional problem but smaller constraints.
Well actually..