Description
Input
Output
Sample Input
31 3 2
Sample Output
1
HINT
题解
由于题目要求我们求严格递增的数列,即:
$$A[i]>A[i-1],1<i<=N$$
我们不妨令B[i]=A[i]-i,那么我们容易得到
$$B[i]>=B[i-1],1<i<=N$$
两式是等价的。
那么我们可以将原数列处理一下,我们只需要求出$B[i]$的最长不下降子序列,把不在序列中的那些数$B[i]$都改成符合条件的数(比如说和左边最近一个在最长不下降子序列中的$B[j]$相等)就能满足题意了。
当然,我们并不需要求出具体的修改方案,我们只需要求出最长不下降的长度$K$,输出$N-K$即可。
注意:
由于数据为$10^5$显然我们要用二分优化求最长不下降子序列长度。同时由于减去了$i$,我们需要将数组初始化为极小值。
1 #include