题目地址：HDU 4521

基本思路是DP。找前面数的最大值时能够用线段树来维护节省时间。

因为间隔要大于d。

所以能够用一个队列来延迟更新，来保证每次询问到的都是d个之前的。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define lson l, mid, rt<<1

#define rson mid+1, r, rt<<1|1

#define LL __int64

const int INF=0x3f3f3f3f;

struct node

{

    int maxv, num;

};

int maxv[400000], a[1100000];

int q_maxv;

void PushUp(int rt)

{

    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);

}

void Update(int p, int x, int l, int r, int rt)

{

    if(l==r)

    {

        maxv[rt]=p;

        return ;

    }

    int mid=l+r>>1;

    if(x<=mid) Update(p,x,lson);

    else Update(p,x,rson);

    PushUp(rt);

}

void Query(int ll, int rr, int l, int r, int rt)

{

    if(ll<=l&&rr>=r)

    {

        q_maxv=max(q_maxv,maxv[rt]);

        return ;

    }

    int mid=l+r>>1;

    if(ll<=mid) Query(ll, rr, lson);

    if(rr>mid) Query(ll,rr,rson);

}

int main()

{

    int n, d, i, j, top;

    node tmp, now;

    while(scanf("%d%d",&n,&d)!=EOF)

    {

        queue<node>q;

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

        }

        memset(maxv,0,sizeof(maxv));

        for(i=0;i<n;i++)

        {

            q_maxv=0;

            if(a[i])

            Query(0,a[i]-1,0,100000,1);

            now.maxv=q_maxv;

            now.num=a[i];

            q.push(now);

            if(i>=d)

            {

                tmp=q.front();

                q.pop();

                Update(tmp.maxv+1,tmp.num,0,100000,1);

            }

        }

        while(!q.empty())

        {

            tmp=q.front();

            q.pop();

            Update(tmp.maxv+1,tmp.num,0,100000,1);

        }

        printf("%d\n",maxv[1]);

    }

    return 0;

}