The Problem In Discussion is : https://codeforces.net/contest/1839/problem/D
Observations:
- The solution will be decreasing.
- The operation in question requires that we remove elements adjacent to zeroes, and then put them in the array anywhere.
- The trick is that we will not do the put, as we can put element anywhere we assume that we put it at the most optimal position, and we don't have to operate on it again.
- So we remove some elements adjacent to zeroes such that remaining elements form an increasing sub-sequence.
- Removed element will be placed optimally at their desired position. - Say you place some zeroes then each zero removes some contiguous sub-array, the 0 is present in this sub-array and sub-arrays of two zeroes don't overlap.
- A sub-array that zero removes, give cost equal to the number of elements in the sub-array.
- Now it is equivalent that each zero is present in the starting of the sub-array that it is removing.
- So this can be solved with dp.
- This problem is very identical to LIS.
- In fact answer for the last query is always n — size_of_lis of the array.
State of dp
dp[i][k][2]:
1. dp[i][k][0] -> minimum no of removed elements upto index i such that you have used k zeros and i'th element is not removed.
2. dp[i][k][1] -> minimum no of removed elements upto index i such that you have used k zeroes and i'th element is removed.
'
Transitions:
1. If we are removing the i'th element, and we have used k zeroes, then, we are talking about dp[i][k][1], the transition would be :
— that we removed the (i-1)th element and we did it in k zeroes so we can continue the removal so dp[i][k][1] be dp[i-1][k][1] + 1 (as we removed the i'th element)
— that we didn't remove the (i-1)th element, so we have to place a zero just before the i'th element so we can remove it. So dp[i][k][1] = dp[i-1][k-1][0] + 1 .
2. If we are not removing the i'th element then we will find a previous element that we have not removed and
that element must be less then i'th element. (Because we have to maintain the sequence in increasing order).
So for all x < i, such that v[x] < v[i] we can say dp[i][j][0] = dp[x][j-1]][0] + (i-x-1 (this term is no. of elements between x and i)).
— there is a special case if i-x-1 is zero means that x is just the prev element of i, then we don't have to give j-1 zeroes before the x th index. so we can say dp[i][j][0] = dp[x][j][0].
Code
https://codeforces.net/contest/1839/submission/216192185
