如果我说我是找标签看到这题来练树状数组的你信吗？
好一道毒瘤的(DP)。
感性理解一下一个结论，我们每次拔苗右端点一定是最右边的玉米。
证明在这篇题解中已经讲得很清楚了对吧。
我主要是讲一下有关(DP)方程的事儿。
一个显然的状态是(f[i][j])表示我们已经处理了前(i)个玉米苗，并对第(i)个玉米苗拔高了(j)次的答案。
方程是(f[i][j]=max{f[k][l]}+1(1leq k<i,0leq lleq j,H[i]+jgeq H[k]+l))
显然这个转移会(TLE)，于是我们考虑优化，找二维前缀(max)，用二维树状数组实现。
等。。等一下，(H[i]+jgeq H[k]+l?)，这个限制用树状数组显然是难以满足的。
那么我们不妨考虑将高度的限制加入状态。
即设(f[i][j][k])表示前(i)个玉米苗，以不超过(j)高度且被操作了不超过(k)次的玉米苗结尾。
限制中就少了高度的限制。然后在用类似背包的思想滚掉(i)这一维即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace AE86
{
const int bufl=1<<15;
char buf[bufl],*s=buf,*t=buf;
inline int fetch()
{
if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
return*s++;
}
inline int read()
{
int a=0,b=1,c=fetch();
while(!isdigit(c)) b^=c=='-',c=fetch();
while(isdigit(c)) a=a*10+c-48,c=fetch();
return b?a:-a;
}
}
const int N=1e4+10;
const int K=5e2+10;
int n,k,Ans,Max,H[N],f[N][K],Tar[N][K];
inline void Insert(int x,int y,int Val)
{
for(;x<=Max+k;x+=x&-x)
for(int j=y;j<=k+1;j+=j&-j)
Tar[x][j]=max(Tar[x][j],Val);
}
inline int Ask(int x,int y)
{
int Sum=0;
for(;x;x-=x&-x)
for(int j=y;j;j-=j&-j)
Sum=max(Sum,Tar[x][j]);
return Sum;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=AE86::read(),k=AE86::read();
for(int i=1;i<=n;i++) H[i]=AE86::read(),Max=max(Max,H[i]);
for(int i=1;i<=n;i++)
for(int j=k;j>=0;j--)
f[i][j]=Ask(H[i]+j,j+1)+1,Insert(H[i]+j,j+1,f[i][j]);
for(int i=1;i<=n;i++)
for(int j=k;j>=0;j--)
Ans=max(Ans,f[i][j]);
printf("%lld
",Ans);
}