p3902 递增（incr）

传送门

然而考试的时候并没有看出来是线性dp

---

那么复习一下线性dp lis问题

LIS 最长上升子序列

可以用dp求解 复杂度O(n^2)

定义dp[i] 表示a[i]为结尾的“最长上升子序列”的长度

转移方程 dp[i]=max{dp[j]+1} (0<=j<i,a[j]<a[i])

边界也很好理解 就是dp[0]=0

那么目标就是max{dp[i]}

---

用一个b数组记录a[i]-i的值（原因请大家思考一下，后面公布）

那么这道题就转化为求解b数组的lis问题

用总个数减去b数组最长上升子序列的个数 就是答案

具体看代码

#include<bits/stdc++.h>
using namespace std;
int n,len;
const int mxn=100005;
int a[mxn],dp[mxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]-=i;
    }
    dp[++len]=a[1];
    for(int i=2;i<=n;i++){
        if(dp[len]<=a[i]) dp[++len]=a[i];
        else{
            int k=lower_bound(dp+1,dp+len+1,a[i])-dp;//二分查找第一个大于等于a[i]的元素位置 
//            cout<<dp<<" "<<lower_bound(dp+1,dp+len+1,a[i]);
            dp[k]=a[i]; 
        } 
    }
    cout<<n-len;
    return 0;
}

 至于为什么用总长减去b数组的lis就是答案

我们可以思考：

1，2，3，4，……，n（后文称为序列g）是严格单调递增的

所谓严格单调递增就是指上升序列（非严格单调递增就是不下降序列）

设a_i>a_i+1 那么 a_i+1-(i+1)< a_i-i

当然也有可能存在a_i<a_j,a_i-i=a_j-j

所以只用求出b数组的非严格单调递增序列就好