---

发现是取一个最长不下降子序列

我们一定可以把一个区间加的右端点放在取出的子序列的最右边，然后就可以dp了

\(dp_{i,j}\)代表前\(i\)个玉米田末尾为\(i\)拔高过\(j\)次的最大答案

\[ dp_{i,j}=\max dp_{k,l}+1(k<i,h_i+j\ge h_k+l) \]

发现可以维护的样子

维护一个\(f_{i,j}\)表示小于等于\(i\)高度(拔过后)拔的次数小于等于\(j\)次的最大值

直接二维树状数组搞就行了

---

Code

#include 
    
     #include 
     
      int max(int x,int y){return x>y?x:y;}int n,m,k,a[10010],f[6010][510];int query(int x,int y){    int ret=-(1<<30);    for(int i=x;i;i-=i&-i)        for(int j=y;j;j-=j&-j)            ret=max(ret,f[i][j]);    return ret;}void modify(int x,int y,int d){    for(int i=x;i<=m;i+=i&-i)        for(int j=y;j<=k;j+=j&-j)            f[i][j]=max(f[i][j],d);}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++) scanf("%d",a+i),m=max(m,++a[i]);    m+=++k;    memset(f,-0x3f,sizeof f);    modify(1,1,0);    int ans=0;    for(int i=1;i<=n;i++)        for(int j=k-1;~j;j--)        {            int yuy=query(a[i]+j,j+1)+1;            ans=max(ans,yuy);            modify(a[i]+j,j+1,yuy);        }    printf("%d\n",ans);    return 0;}
     
    

---

2019.2.22