AloWarshik's blog

Need a help!
By AloWarshik, history, 32 hours ago, In English

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.

task link

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
31 hour(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

for a particular i let ind1 be the max index ind1<i such that a[ind1]>a[i] and ind2 be the min index ind2>i such that a[ind2]>a[i] then for a particular j(<=k) update (dp[i][j],dp[i+1][j],dp[i+2][j],....dp[ind2-1][j]) with a[i]+min(dp[ind1][j-1],dp[ind1+1][j-1],....dp[i-1][j-1]), dp[n-1][k] would be answer

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ohhh, ok i got it, tysm

    → Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn, my furend spamming dislike ૮(˶ㅠ︿ㅠ)ა

→ Reply