I was solving IZhO task on oj.uz platform and i met a DP problem. I've never solved such problem, so i was confused about solution.
The statement:
We have an array A (1 ≤ Ai ≤ 1000000) with size N (1 ≤ N ≤ 100000) . And we need to divide array into exactly K (1 ≤ K ≤ min(N, 100)) blocks, so the sum of maximums in each block is minimized. Sample:
Input:
6 3
5 3 1 2 4 2
Output:
10
Blocks (1, 2), (3, 3), (4, 6)
I solved it for N * N * K using dp[i][x] with transition to every dp[j][x + 1] (i + 1 <= j <= n); my solution
And i looked for editorial but i didn't find it and i looked for full solution from submissions but i didn't understand it. If you can clearly explain how to solve it and prove it, please help.
