You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.
1≤N≤100000, 1≤K≤min(N, 100)
http://izho.kz/2014/uploads/izho_day2_en_info.pdf
There are some solutions which is N * K * log(N), like monotonic queue + segment tree. But I'm not sure about this complexity works in 1 second.
Is there any better approach?
EDIT : Thank you ko_osaga for solution, and good explanation!
Here is the code.
There is an O(NK) algorithm which utilizes two stacks and sweeping.
If you are interested, see this code : http://oj.uz/submission/13117
Can you explain your approach? I only know N^2*K dp approach
DP Formula is : dp[i][j] = Min(j < k)(dp[i-1][k] + Max(k+1,j)). Naive calculation of these can be done in O(N^2K).
For further optimization, We can associate the values between Max(i,j) and dp[i][j].
DP[i-1] : [1,2,3,4,5,6,7,6,9] Array[] : [3,1,4,1,5,9,2,6,5]
Max(8,9) and Max(9,9) differs, which means Array[9] can only be mapped with dp[i-1][8].
Max(6,9) and Max(7,9) differs, but Max(7,9) == Max(8,9). which means Array[7 ~ 8] can be mapped with dp[i-1][6 ~ 7].
Now, my solution will model those two arrays into stacks. The element in stacks fill this conditions : DPStack[s-1] + ArrStack[s-1] >= DPStack[s] + ArrStack[s], ArrStack[s-1] >= ArrStack[s].
When new DP[i-1] and Array[i] is inserted in stack, both stacks are popped while ArrStack.top() < Array[i]. While popping the values, look for the dp values popped in the stack — we should pick the smallest from the popped element, and set it as the associated values for Array[i]. (Since the value from stack is smaller than Array[i], it can be associated with Array[i].)
Now, we should insert those values (Array[i] and it's associated dp) into stacks only if the values are the smallest. Since every elements are popped and inserted into stack for one time, this algorithm has linear time complexity.
If you still can't understand, feel free to ask me. Also, there is a simillar problem in US Open 2012 — check it if you want to. http://www.usaco.org/index.php?page=viewproblem2&cpid=138
I can't understand why the first observation is right.
Array = {100,100,1}
Now dp[2][2] = 200 and dp[2][3] = 101.
My bad. I was confused over this problem and another problem in link. I will fix that part.
(*Fixed.)
I don't understand. Why does DPStack[s-1] + ArrStack[s-1] >= DPStack[s] + ArrStack[s] hold?
It's not like they naturally hold, but we are adding the value that only satisfies such condition. You don't need to add a value with DPStack[s-1] + ArrStack[s-1] < DPStack[s] + ArrStack[s] as it's never a better choice than s-1 when you need it.
Auto comment: topic has been updated by kalimm (previous revision, new revision, compare).
Also divide and conquer optimization doesn't work for this one. Sorry about that. Fixed.