这道题实在是一道 毒瘤 题，太坑爹了。那个写 \(deque\) 的题解亲测只有80分，原因 **不言而明 **，这道题居然 丧心病狂 到 卡STL 。

---

好了，不吐槽了，进入正题

题目分析：

这是一道十分 简单 的DP，相信大家也可以很容易地吧DP状态转移方程给推出来。我就献丑给大家推一遍，如有错漏，请留言，谢谢。
我们可以定一个函数 \(f(i)\) ,它表示跳到 \(i\) 棵树上去的 \(f(i)\) 的劳累值。由题可知，可以 \(i-v,i-v+1,i-v+2,......i-2,i-1\) 棵树上跳到 \(i\) 棵树，所以可以推出DP状态转移方程 \(f(i)=min\{f(j)+(h(i)>=h(j))\},j\in[i-v,i)\)
时间复杂度： \(\Theta(n^2)\) , 空间复杂度： \(\Theta(n)\) 。

---

code 1:

#include<bits/stdc++.h>

#define Maxn 1000010

#define int long long

using namespace std;

int n;

int h[Maxn];

int p;

int f[Maxn];

signed main()

{

    scanf("%lld",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&h[i]);

    }

    scanf("%lld",&p);

    while(p--)

    {

        memset(f,0,sizeof(f));

        int v;

        scanf("%lld",&v);

        f[1]=0;

        for(int i=2;i<=n;i++)

        {

            int tmp=0x80000000;

            for(int j=i-v;j<i;j++)

            {

                tmp=min(tmp,f[j]+(h[i]>=h[j]));

            }

            f[i]=tmp;

        }

        printf("%lld\n",f[n]);

    }

    return 0;

}

记录：5AC，4RE，1TLE

---

优化 1：

我们考虑用单调队列优化,将其优化成 \(\Theta(n)\) 。作为一个钟爱于STL的 Oler，我选择了方便而又快捷的 \(deque\) 。

我们用单调队列维护 \(f(j)+(h(i)>=h(j))\) 。维护 \(f(j)\) ,将队列中 \(f(j)\) 严格 单调递减，使得队列中的 \(f(j)\) 取出来时永远是最小的；在队尾的 \(f(j)\) 相等时，我们还要将队列中的 \(height(j)\) 进行维护，使得队列中的 \(height(j)\) 单调递增，使得队列中的 \(height(j)\) 的队首取出来永远是是最大的，使得 \((h(i)>=h(j))\) 尽量为0。

去头就简单了，假如 \(j\) 是过期的数据，即 \(j<i-v\) ,我们就把 \(j\) 给 \(pop\) 掉。

---

code 2:

#include<bits/stdc++.h>

#define Maxn 1000010

#define int long long

using namespace std;

int n;

int h[Maxn];

int p;

int f[Maxn];

struct node

{

    int id,v;

};

deque<node>dq;

signed main()

{

    scanf("%lld",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&h[i]);

    }

    scanf("%lld",&p);

    while(p--)

    {

        memset(f,0,sizeof(f));

        dq.clear();

        int v;

        scanf("%lld",&v);

        dq.push_back((node){1,0});

        for(int i=2;i<=n;i++)

        {

            while(!dq.empty()&&dq.front().id<i-v)

            {

                dq.pop_front();

            }

            f[i]=dq.front().v+(h[i]>=h[dq.front().id]);

            while(!dq.empty()&&(dq.back().v>f[i]||(dq.back().v==f[i]&&h[i]>=h[dq.back().id])))

            {

                dq.pop_back();

            }

            dq.push_back((node){i,f[i]});

        }

        printf("%lld\n",f[n]);

    }

    return 0;

}

记录：8AC，2TLE

---

优化 2：

题目太过于 毒瘤 ，卡掉了STL，使得STL惨遭TLE，所以我们考虑数组模拟 \(deque\) 。

定义头指针 \(head\) ，尾指针 \(tail\) ，通过移动头尾指针，来模拟 \(deque\) 。 \(pop\_front\) 即为 \(head++\) , \(pop\_back\) 即为 \(tail--\) 。我们很轻松就可以AC了。

注：

STL好用是好用，但一定要注意STL的劣势，那就是在调用函数的时候比数组慢太多。一般来说，STL不会被卡；但难保有如此一道像这一道一样的毒瘤题呢？！

---

code 3：

#include<bits/stdc++.h>

#define Maxn 1000010

#define int long long

using namespace std;

inline void read(int &x)

{

    int f=1;x=0;char s=getchar();

    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int n;

int h[Maxn];

int p;

int f[Maxn];

struct node

{

    int id,v;

};

node que[Maxn];

signed main()

{

    read(n);

    for(int i=1;i<=n;i++)

    {

        read(h[i]);

    }

    read(p);

    while(p--)

    {

        memset(f,0,sizeof(f));

        memset(que,0,sizeof(que));

        int v;

        read(v);

        que[1].id=1;

        que[1].v=0;

        int head=1;

        int tail=2;

        for(int i=2;i<=n;i++)

        {

            while(head<tail&&que[head].id<i-v)

            {

                head++;

            }

            f[i]=que[head].v+(h[i]>=h[que[head].id]);

            while(head<tail&&(que[tail].v>f[i]||(que[tail].v==f[i]&&h[i]>=h[que[tail].id])))

            {

                tail--;

            }

            que[++tail].id=i;

            que[tail].v=f[i];

        }

        printf("%lld\n",f[n]);

    }

    return 0;

}

记录：10AC

---

最后，给你一个 \(struct\) 封装的 \(deque\) 。

code 4:

#include<bits/stdc++.h>

#define Maxn 1000010

#define int long long

using namespace std;

inline void read(int &x)

{

    int f=1;x=0;char s=getchar();

    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int n;

int h[Maxn];

int p;

int f[Maxn];

int que_id[Maxn],que_v[Maxn];

struct dque

{

    int head,tail;

    dque()

    {

        head=1;

        tail=0;

    //	memset(que,0,sizeof(que));

    }

    inline bool empty()

    {

        return head>tail;

    }

    inline int front_id()

    {

        return que_id[head];

    }

    inline int front_v()

    {

        return que_v[head];

    }

    inline int back_id()

    {

        return que_id[tail];

    }

    inline int back_v()

    {

        return que_v[tail];

    }

    inline void pop_front()

    {

        head++;

    }

    inline void pop_back()

    {

        tail--;

    }

    inline void push_back(int id,int v)

    {

        que_id[++tail]=id;

        que_v[tail]=v;

    }

    inline void clear()

    {

        head=1;

        tail=0;

    }

}dq;

signed main()

{

    read(n);

    for(int i=1;i<=n;i++)

    {

        read(h[i]);

    }

    read(p);

    while(p--)

    {

        memset(f,0,sizeof(f));

        dq.clear();

        int v;

        read(v);

        dq.push_back(1,0);

        for(int i=2;i<=n;i++)

        {

            while(!dq.empty()&&dq.front_id()<i-v)

            {

                dq.pop_front();

            }

            f[i]=dq.front_v()+(h[i]>=h[dq.front_id()]);

            while(!dq.empty()&&(dq.back_v()>f[i]||(dq.back_v()==f[i]&&h[i]>=h[dq.back_id()])))

            {

                dq.pop_back();

            }

            dq.push_back(i,f[i]);

        }

        printf("%lld\n",f[n]);

    }

    return 0;

}

记录：9AC，1TLE

---

如果作者有疏漏或错误的地方，请私信给我，或在评论中留言，谢谢。

洛谷P3572题解的相关教程结束。