考试最后半个小时才做这道题。十分钟写了个暴力还写挂了。。最后默默输出n。菜鸡一只。
这道题比较好看出来是动规。首先我们要明确一点。因为能拔高长度任意的一段区域，所以如果从i开始拔高，那么一直拔高到n比一直拔高到j更优。因为j~n变高了对于答案是有利的。
我们定义f[i][j]表示到第i个点前面拔高j次的最大剩余数。在i点的高度为hei[i]+j（因为前面拔高j次，最终都会拔高到n）。所以我们要找在高度小于hei[i]+j，次数小于j里面最大剩余数+1去更新。而找这个有限制的二维前缀最大值，可以用二维树状数组去维护。
注意：
①树状数组第一维最大是heimax+k，第二维最大为k，而不是n
②k可以为0，但是如果为0的话树状数组是跳不出来的。所以我们初始就让k++，让k=1代表k=0
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 11000
int n,k;
int hei[N];
int f[N][510];
int c[N][510];
int maxhei;
int lowbit(int x){
return x&(-x);
}
void add(int i,int j,int num){
for(int ii=i;ii<=maxhei+k;ii+=lowbit(ii))
for(int jj=j;jj<=k;jj+=lowbit(jj))
c[ii][jj]=max(c[ii][jj],num);
}
int tot(int i,int j){
int sum=0;
for(int ii=i;ii;ii-=lowbit(ii))
for(int jj=j;jj;jj-=lowbit(jj))
sum=max(sum,c[ii][jj]);
return sum;
}
int main(){
scanf("%d%d",&n,&k);
pos(i,1,n){
scanf("%d",&hei[i]);
maxhei=max(maxhei,hei[i]);
}
k++;
pos(i,1,n){
pos2(j,k,1){
f[i][j]=max(f[i][j],tot(hei[i]+j,j)+1);
add(hei[i]+j,j,f[i][j]);
}
}
cout<<tot(maxhei+k,k);
while(1);
return 0;
}