【 $\Theta(nk\log n)$的解法 】

显然的,拔高一个区间的玉米,右端点一定是第n株玉米。

于是我们列出状态转移方程:

F[i][k] 为第i株玉米,拔高用了 k 次的最长不降序列。

F[i][k]=max(F[i][k],F[j][k-l]+1); (j<k,A[i]>=A[j]+l)    

但是这样的时间复杂度是 $\Theta(n^2k^2)$的。

试着将复杂度降到 $\Theta(n\times k^2\times \log n)$

也就是说,当l确定的时候,我们要快速找出F[j][k-l]

容易想起求最长不降序列的套路:我们引入 $k$ 个树状数组,这样就可以快速求解了。

for(int i=1;i<=n;++i)
{
    for(int k=1;k<=n;++k)
    {
        for(int l=1;l<=k;++l)
            F[i][k]=max(Query(A[k]+l)+1,F[i][k]);
    }
}

但是这样还不够。

思维转化

我们先是很轻松的想到了二维树状数组。

for(int i=1; i<=n; ++i) 
    {
        for(int j=k; j>=0; --j) // 防止继承了 i 的状态。
        {
            x=Query(j+1,A[i]+j)+1; // 由于树状数组的feature ,我们不得不将 j 整体+1
            smax(ans,x);
            Add(j+1,A[i]+j,x);
        }
    }

Query(state,height) 函数的作用是找到最大的F[i][state](A[i]<height)

我们把这个树状数组想象成一个平面:

gra.png

上面代码的查找过程是 黄色-->橙色-->红色。

容易发现这样会有很多重复。

我们发现新增的状态只有两条。

gra.png

于是我们可以拿两个树状数组维护新增的状态!

最优解第二代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
#include<queue>
#include<iostream>
#include<cctype>
#include<cmath>
//#define int long long 
using namespace std;
inline int gi(){short tmp=getchar();int flag=1;while(!isdigit(tmp)){if(tmp=='-'){flag=-1;tmp=getchar();break;}tmp=getchar();}int ans=0;while(isdigit(tmp)) {ans=(ans<<3)+(ans<<1)+tmp-'0';tmp=getchar();}return ans*flag;}
inline void write(int x){static int stk[100], top = 0;if (x == 0) { putchar('0'); putchar(' ');return; }if (x < 0) { x = -x; putchar('-'); }while (x) { stk[++top] = x % 10; x /= 10; }while (top) { putchar(stk[top--] + '0'); }putchar(' ');}
#define line() putchar('\n');
#define Mem(Arr,V) memset(Arr,V,sizeof Arr);
#define Mcpy(Arr,qwq) memcpy(Arr,qwq,sizeof qwq);
#define max3(a,b,c) max(max(a,b),c)
#define max4(a,b,c,d) max4(max3(a,b,c),d);
#define in(a) a=gi()
#define in2(a,b) in(a),in(b)
#define in3(a,b,c) in2(a,b),in(c)
#define in4(a,b,c,d) in3(a,b,c),in(d)
#define write2(a,b) write(a),write(b)
#define write3(a,b,c) write2(a,b),write(c)
#define write4(a,b,c,d) write3(a,b,c),write(d)
inline void smin(int &x,int y){x=min(x,y);}
inline void smax(int &x,int y){x=max(x,y);}
const int inf = 1000000;
const int K =540;
int Height[522][5522],State[522][5522];
inline int lowbit(int x){return x&-x;}
inline void Add(int *A,int pos,int v,int to)
{
    for(int i=pos;i<=to;i+=lowbit(i))
        smax(A[i],v);
}
inline int Query(int *A,int pos)
{
    int ans=0;
    for(int i=pos;i>0;i-=lowbit(i))
        smax(ans,A[i]);
    return ans;
}
inline void AddH(int pos,int num,int v,int to)
{
    for(int i=pos;i<=to;i+=lowbit(i))
    {
        smax(Height[i][num],v);
    }
}
inline int QueryH(int pos,int num)
{
    int ans=0;
    for(int i=pos;i>0;i-=lowbit(i))
    {
        smax(ans,Height[i][num]);
    }
    return ans;
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("data.in","r",stdin);
    #endif
    int n,k;in2(n,k);
    int ans=0,x=0;
    int A;
    for(int i=1; i<=n; ++i) 
    {
        A=gi();
        for(int j=0; j<=k; ++j) // 这种方式不用考虑逆序问题! 看图!
        {
            int q1=Query(State[j+1],A+j);
            int q2=QueryH(j+1,A+j);
            x=max(q1,q2)+1;smax(ans,x);
            Add(State[j+1],A+j,x,5502);
            AddH(j+1,A+j,x,502);
        }
    }
    write(ans);
    return 0;
}