学步园

题目描述

数列 A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。

输入格式

第 1 行，1 个整数 N
第 2 行，N 个整数 A1,A2,...,AN

输出格式

1 个整数，表示最少修改的数字

样例输入

3
1 3 2

样例输出

1

数据范围

对于 50% 的数据，N ≤ 10^3
对于 100% 的数据，1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9

题解

这道题是河南06年省选一试的弱化版。nlogn的最长不降子序列要普及。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
#define ll long long
#define inf 1e15
using namespace std;
int n,f[MAXN],ans=1,l,r;
ll a[MAXN],b[MAXN];
void init()
{
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
	   {scanf("%I64d",&a[i]);
	    a[i]=a[i]+n-i+1;
	   }
}
int erf(ll x)
{
	int s=l,t=r,mid,w;
	while(s<=t)
	   {mid=(s+t)>>1;
	    if(b[mid]<=x) w=mid,s=mid+1;
	    else t=mid-1;
	   }
	return w;
}
void dp()
{
	int i,w;
	for(i=1;i<=n;i++) b[i]=inf;
	f[1]=1; b[1]=a[1]; b[0]=-inf;
	l=0; r=1;
	for(i=2;i<=n;i++)
	   {w=erf(a[i]);
	    f[i]=w+1; b[w+1]=min(b[w+1],a[i]);
	    if(w==r) r++;
	    ans=max(ans,f[i]);
	   }
	printf("%d\n",n-ans);
}
int main()
{
	freopen("incr.in","r",stdin);
	freopen("incr.out","w",stdout);
	init(); dp();
	return 0;
}