Description
给你一个长度为$n$的序列$A$.现在准许你删除任意一个数，删除之后需要修改最小的次数使序列单调递增。问最小次数。
$1≤n≤200000$
Examples
Input
5
5 4 3 2 1
Output
3
Input
5
1 2 8 9 5
Output
0
因为是修改形成递增，所以假设修改$l+1~r-1$，那么要求$a[r]-a[l]-1>=r-l-1$
于是有$a[r]-r>=a[l]-l$
于是就转化为求最长不下降子序列
因为可以删一个点，删掉的点的后面的值减去的位权-1
设$f[i][0/1]$为第i位，是否删了点
用二分优化，重新令$f[i][0/1]$表示长为i的序列末尾最小的数，是否删点
注意删了点的话位置会向前移，所以由$a[i]-i$变成$a[i]-i+1$
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int inf=1e9,f[200005][2],a[200005],b[200005],n,tot,ans; 8 int find(int x,int p) 9 { 10 int l=1,r=n,as=0; 11 while (l<=r) 12 { 13 int mid=(l+r)/2; 14 if (f[mid][p]>x)as=mid,r=mid-1; 15 else l=mid+1; 16 } 17 return as; 18 } 19 int main() 20 {int i,tmp1,tmp2; 21 cin>>n; 22 for (i=1;i<=n;i++) 23 { 24 scanf("%d",&a[i]); 25 f[i][0]=f[i][1]=inf; 26 } 27 f[0][0]=f[0][1]=-inf; 28 for (i=2;i<=n;i++) 29 { 30 tmp1=find(a[i-1]-i+1,0);tmp2=find(a[i]-i+1,1); 31 f[tmp1][0]=a[i-1]-i+1; 32 f[tmp2][1]=a[i]-i+1; 33 f[tmp1][1]=min(f[tmp1][1],f[tmp1][0]); 34 ans=max(ans,max(tmp1,tmp2)); 35 } 36 cout<<n-ans-1; 37 }