使用 cdq 分治

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int c[N],n,k;
int lb(int x){return x&-x;}
int qry(int x,int res=0){for(;x;x-=lb(x)) res=max(res,c[x]);return res;}
void upd(int x,int y){for(;x<N;x+=lb(x)) c[x]=((~y)?max(c[x],y):0);}
struct P{
	int f[505],val;
}a[N];
void sol(int l,int r){
	if(l>r) return;
	if(l==r){
		for(int i=0;i<=k;i++) a[l].f[i]=max(a[l].f[i],1);
		return;
	}
	int mid=l+r>>1;
	sol(l,mid);
	for(int j=0;j<=k;j++){
		for(int i=l;i<=mid;i++) upd(a[i].val+j,a[i].f[j]);
		for(int i=mid+1;i<=r;i++) a[i].f[j]=max(a[i].f[j],qry(a[i].val+j)+1);
	}
	for(int j=0;j<=k;j++) for(int i=l;i<=mid;i++) upd(a[i].val+j,-1);
	sol(mid+1,r);
}
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].val);
	sol(1,n);
	printf("%d\n",a[n].f[k]);
	return 0;
}
//f[i][k1]=max(f[j][k2])+1 a[i]+k1>=a[j]+k2,k1>=k2,i>=j