emmm...我真的太懒了,老是拖欠,有些题写完就忘了,但尽管如此,我还是拖欠...这两天更是罪大恶极的打了两天LOL,呜呜呜.好了,废话就这么多.

这题是树状数组维护的dp,怎么维护呢.在维护dp前,我们必须要知道一个性质.什么性质呢,就是你选区间的时候鸭,区间的右端点一定是n(证明:因为假如不在最右边,那么右边的一段有些相对高度会降低,那么对于答案会产生不好的影响.),所以我们拿个树状数组,维护两种元素.
1.这个点作为左端点选了多少次.
2.这个点的高度有多高.
维护这两个条件下的最长序列即可.
对于这个树状数组的区间最值来说,你会发现,他只会在max更新,而不会把一个值更新到小的,如此,我们直接dp即可.注意枚举k的时候应该倒着枚举,因为不可能让自己的信息更新自己本身对吧.

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+600,K=521;
int tr[N][K];//值为i,拔高j次.
int a[N];
int lowbit(int x)   { return x&(-x);  }
int n,k,mx;

inline void add(int x,int y,int z)
{
    for(register int i = x;i <= mx+ k; i += lowbit(i))
        for(register int j = y;j <= k + 1; j += lowbit(j))
            tr[i][j] = max(tr[i][j],z);
}

inline int query(int x,int y)
{
    int ans = 0;
    for(register int i = x;i; i -= lowbit(i))
        for(register int j = y;j; j -= lowbit(j))
            ans = max(ans,tr[i][j]);
    return ans;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        mx=max(mx,a[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=k;j>=0;j--)
        {
            int temp=query(a[i]+j,j+1)+1;
            ans=max(ans,temp);
            add(a[i]+j,j+1,temp);
        }
    }
    printf("%d\n",ans);
    return 0;
}