The Problem In Discussion is : https://codeforces.net/contest/1839/problem/D
Observations:
- The solution will be decreasing.
- Say you place some zeroes then each zero removes some contiguous subarray, the 0 is present in this subarray and subarrays of two zeroes don't overlap.
- A subarray that zero removes, give cost equal to the number of elements in the subarray.
- Now it is equivalent that each zero is present in the starting of the subarray 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[j] < 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].