rt.

在做 P3902 递增 时，起先用了朴素 dp 求 LIS，然后 WA 10pts（别在意为什么提交的人不是我，用小号交的）.

$O(n^2)$ Code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <array>
#include <map>
#include <bitset>
#include <vector>
#include <cstring>
#define int long long
using namespace std;

void read(int &x){
	x=0; int f=1; char ch=getchar();
	while(ch<'0' || ch>'9') f=(ch=='-')?-1:1,ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	x=x*f;
}

const int N=2e3+5;

int n,m;
int a[N],b[N],f[N];

signed main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i]-i;
	for(int i=1;i<=n;i++) f[i]=1;
	
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			if(b[j]<=b[i])
				f[i]=max(f[i],f[j]+1);
	
	printf("%lld\n",n-f[n]);
	return 0;
}

然后痛定思痛，决定用 $O(n \log n)$ 的复杂度求 LIS，然后 AC 了。

$O(n \log n)$ Code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <array>
#include <map>
#include <bitset>
#include <vector>
#include <cstring>
#define int long long
using namespace std;

void read(int &x){
	x=0; int f=1; char ch=getchar();
	while(ch<'0' || ch>'9') f=(ch=='-')?-1:1,ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	x=x*f;
}

const int N=2e3+5;

int n,m,len;
int a[N],b[N],f[N];

signed main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i]-i;
	for(int i=1;i<=n;i++) f[i]=1;
	
	f[++len]=b[1];
	for(int i=2;i<=n;i++){
		if(b[i]>=f[len]) f[++len]=b[i];
		else *lower_bound(f+1,f+len+1,b[i])=b[i];
	}
	
	printf("%lld\n",n-len);
	return 0;
}

显然，中间 LIS 部分都是在求 b 数组的 LIS，为什么结果会不同？求教了。