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

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

解题思路

先设 $f(i)$ 表示到 $i$ 的最小劳累值。

很容易得出转移：

$f(i)=\min(f(j)/f(j)+1)$

其中 $f(j)/f(j)+1$ 由 $d_i$ 和 $d_{j}$ 的大小关系决定，并且 $i-k\leq j <i$ 。

很显然，直接暴力是 $O(n^2)$ 的，会超时。

于是，考虑优化。

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

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

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

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

于是，时间复杂度降为 $O(nq)$

代码

#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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/461908.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！