题目链接

https://www.51nod.com/Challenge/Problem.html#problemId=1294

解题思路

如果a[i]-i<0，必须修改；
求由a[i]-i组成的序列的最长非严格递增子序列，其长度为无需修改的数量；
为什么？
保证严格递增就有a[i]-a[j]>=i-j (i>j)，变形得 a[i]-i>=a[i]-j，即要求a[i]-i序列非严格单调递增即可，最长的长度就是无需修改的最大长度。
最后输出n-最长非严格单调递增序列长度。

AC代码

#include<bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld",x)
using namespace std;
const int N=1e5+10;
const ll inf=1e9+100;
ll ans,p[N],a[N],dp[N],n,num;
int main(){
    sc(n);
    for(int i=1;i<=n;i++){
        sc(a[i]);
        if(a[i]-i>=0) p[++num]=a[i]-i;
    } 
        //核心，求最长非严格单调递增子序列长度
    fill(dp,dp+N+1,inf);
    for(int i=1;i<=num;i++) *upper_bound(dp+1,dp+num+1,p[i])=p[i];
    pr(n-(lower_bound(dp+1,dp+num+1,inf)-dp-1));
}

另附：最长严格单调递增子序列长度

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int N=1e4;
int n,a[N],dp[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
        //核心
    fill(dp,dp+N+1,inf);
    for(int i=1;i<=n;i++) *upper_bound(dp+1,dp+n+1,a[i])=a[i];
    cout<<lower_bound(dp+1,dp+n+1,inf)-dp-1<<endl;
}

总结

1.显然，这只能用来求长度，不可以用来求序列，求出来的序列并不一定是正确的。
2.思路是真不好想。