[POI2014] PTA-Little Bird（单调队列优化 DP）

luogu 传送门https://www.luogu.com.cn/problem/P3572

解题思路

先设  表示到  的最小劳累值。

很容易得出转移：

其中  由  和  的大小关系决定，并且 。

很显然，直接暴力是  的，会超时。

于是，考虑优化。

我们发现  是有一定的取值范围，并且我们取的是这个区间内的最小值。

也许这可以用单调队列优化。

判断对头是否在范围内，如果不在即出队；

入队的时候，考虑队尾的劳累值是否大于当前的劳累值，如果大于，则队尾出队，如果队尾的劳累值等于当前的劳累值，我们可以比较谁的高度更高，保留更高的（因为更高的对后面的情况更优）。

于是，时间复杂度降为 

代码

#include<bits/stdc++.h>
using namespace std;int n;
int d[1000001];
int qi;
int ki;
int f[1000001];
int q[1000001];
int head,tail;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>d[i];}cin>>qi;while(qi--){cin>>ki;head=1,tail=0;f[1]=0;q[++tail]=1;for(int i=2;i<=n;i++){while(head<=tail&&q[head]<i-ki)head++;if(d[i]>=d[q[head]])f[i]=f[q[head]]+1;elsef[i]=f[q[head]];while(head<=tail&&(f[q[tail]]>f[i]||(f[q[tail]]==f[i]&&d[q[tail]]<=d[i])))tail--;q[++tail]=i;} cout<<f[n]<<endl;}return 0;
}