题意
进行最多 \(k\) 次区间 \(+1\) 操作，使得序列中的最长不下降子序列最长。
分析
首先，拔高的区间一定是 \([i,n]\) 这种的，因为拔高一段区间，对于区间内部的相对高度是不变的，而对于区间左边，可能会使整体答案变大，但对于区间右边，答案可能会变小，所以对于最优解，区间右边绝对没有玉米。
假设拔高了 \([i,n]\) 这段区间，那么 \(a_i\) 必将存在于答案的序列中，不然没有必要拔高它。
设 \(dp_{i,j}\) 表示拔高了 \(j\) 每次拔高区间左端点小于等于 \(i\),并以 \(a_i\) 结尾的最长不下降子序列的长度。
显然,\(dp_{i,j}=max(dp_{x,y})+1,(x \leq i,y \leq j,a_x+y \leq a_i + j)\),因为 \(x\leq i\)，在转移时恒成立，所以只需要保证 \(y \leq j,a_x+y \leq a_i + j\)即可，且 \(a_i\)的范围比较小，考虑用二维树状数组维护满足条件的最大值。复杂度 \(O(N K \log K \log (max(a_i+K)))\)。
一些注意事项
- 树状数组不能维护等于 \(0\) 的情况，所以需要整体右移，详见代码。
- 在枚举 \(j\) 的时候需要倒序，原理跟 \(01\) 背包压维类似。
\(code\)
#include<bits/stdc++.h>
#define N 10005
#define MX 5505
#define K 505
#define max(a,b) (a>b?a:b)
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,k,mx;
int a[N],c[K][MX],dp[N][K];
void add(int x,int y,int d){
for(int i=x;i<=k+1;i+=i&(-i))
for(int j=y;j<=mx;j+=j&(-j))
c[i][j]=max(c[i][j],d);
}
int ask(int x,int y){
int sum=0;
for(int i=x;i;i-=i&(-i))
for(int j=y;j;j-=j&(-j))
sum=max(sum,c[i][j]);
return sum;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);
mx+=k;
for(int i=1;i<=n;i++)
for(int j=k;j>=0;j--) //倒序枚举
add(j+1,a[i]+j,dp[i][j]=ask(j+1,a[i]+j)+1); // j+1 整体右移
printf("%d\n",ask(k+1,mx));
return 0;
}