首页 > 代码库 > Bzoj 3831: [Poi2014]Little Bird
Bzoj 3831: [Poi2014]Little Bird
3831: [Poi2014]Little Bird
题目大意：从1开始，跳到比当前矮的不消耗体力，否则消耗一点体力，每次询问有一个步伐限制，求每次最少耗费多少体力
f[i]表示跳到i位置消耗的最小体力
从单调队列中取数，维护的东西有三个
1.单调队列的范围维持在K以内
2.队列尾部位置对应的答案与当前枚举到的位置对应的答案相比，当前答案更优时（f[now]最小时），弹出尾元素
3.队列尾部位置对应的答案与当前枚举到的位置对应的答案相同时，比较当前位置的高度和队尾位置的高度，队尾元素较低的话，弹出尾元素
一系列维护之后，将当前点放入队尾
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,m,q[1000010],H[1000010],f[1000010];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&H[i]); scanf("%d",&m); int h,t; for(int j=1;j<=m;j++){ h=t=1; int k;scanf("%d",&k); memset(q,0,sizeof(q)); memset(f,0,sizeof(h)); q[t++]=1; for(int i=2;i<=n;i++){ while(h<t&&i>q[h]+k)h++; f[i]=f[q[h]]+(H[q[h]]>H[i]?0:1); while(h<t&&(f[q[t-1]]>f[i]||(f[q[t-1]]==f[i]&&H[q[t-1]]<=H[i])))t--; q[t++]=i; } printf("%d\n",f[n]); }}
Bzoj 3831: [Poi2014]Little Bird
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。