lp3902 递增

最长上升子序列裸题。
dp+二分即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

int main(){
	init();
	return 0;
}