题目描述
方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。
这排玉米一共有N株，它们的高度参差不齐。
方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米，来构成一排美丽的玉米。
输入
第1行包含2个整数n，K，分别表示这排玉米的数目以及最多可进行多少次操作。
第2行包含n个整数，第i个数表示这排玉米，从左到右第i株玉米的高度ai。
输出
输出1个整数，最多剩下的玉米数。
样例输入
3 1
2 1 3
样例输出
3
提示
1 < N < 10000，1 < K ≤ 500，1 ≤ ai ≤5000
题解
仿佛耳熟能详的一道题，但是从来没有读过题面，原来是二维树状数组优化dp。f[i][j]表示到第i根玉米用j次拔高最多能留下多少根，显然区间选取从某点到n更有利于后面的点被选取(又是贪心思路)，可写出f[i][j]=max{f[x][y]，x<i,y<=j,a[x]+y<=a[i]+j},第一个条件是随着时间轴自然而然就满足的，后两个要求一个范围，可以用树状数组来优化。用二维树状数组(人生第一题)存储区间最大值，就可以方便地query转移了。
void update(int x,int y,int z)
{
for(int i=x;i<=k+1;i+=lowbit(i))
for(int j=y;j<=jd;j+=lowbit(j))
bj(sz[i][j],z);
}
int query(int x,int y)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
bj(res,sz[i][j]);
return res;
}#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int sj=;
int n,k,a[sj],f[sj][],jd,jg,sz[][];
int bj(int &x,int y)
{
x=x>y?x:y;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y,int z)
{
for(int i=x;i<=k+;i+=lowbit(i))
for(int j=y;j<=jd;j+=lowbit(j))
bj(sz[i][j],z);
}
int query(int x,int y)
{
int res=;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
bj(res,sz[i][j]);
return res;
}
inline int r()
{
int zty=,jk=;
jk=getchar()-'';
if(jk>=&&jk<=) zty+=jk;
jk=getchar()-'';
while(jk>=&&jk<=)
{
zty*=;
zty+=jk;
jk=getchar()-'';
}
return zty;
}
int main()
{
n=r();
k=r();
for(int i=;i<=n;i++)
{
a[i]=r();
bj(jd,a[i]);
}
jd+=k;
for(int i=;i<=n;i++)
for(int j=k+;j>=;j--)
{
bj(f[i][j],query(j,a[i]+j-)+);
bj(jg,f[i][j]);
update(j,a[i]+j-,f[i][j]);
}
printf("%d",jg);
return ;
}