这道题实在是一道 毒瘤 题，太坑爹了。那个写 \(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;
}
优化 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;
}
优化 2：
题目太过于 毒瘤 ，卡掉了STL，使得STL惨遭TLE，所以我们考虑数组模拟 \(deque\) 。
定义头指针 \(head\) ，尾指针 \(tail\) ，通过移动头尾指针，来模拟 \(deque\) 。 \(pop\_front\) 即为 \(head++\) , \(pop\_back\) 即为 \(tail--\) 。我们很轻松就可以AC了。
注：
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;
}
最后，给你一个 \(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;
}