首页 > 代码库 > 【BZOJ3831】【POI2014】Little Bird 单调队列，''再不刷它就土了''系列。
【BZOJ3831】【POI2014】Little Bird 单调队列，''再不刷它就土了''系列。
题意：
我直接粘bzoj的黑版翻译吧~
有一排n棵树，第i棵树的高度是Di。
MHY要从第一棵树到第n棵树去找他的妹子玩。
如果MHY在第i棵树，那么他可以跳到第i+1,i+2,...,i+k棵树。
如果MHY跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。
为了有体力和妹子玩，MHY要最小化劳累值。
题解：单调队列破题水，没了。
话说BZOJ的POI一向土豪，趁着它还没土赶紧刷了吧。。
不懂再看代码吧，里面有注释
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define inf 0x3f3f3f3f
using namespace std;
int q[N],top,tail,n;
int f[N],high[N];
bool cmp(int ha,int fa,int hb,int fb) // 返回A是否比B优
{
return fa==fb?ha>=hb:fa<fb;
// Ⅰ. 同等代价肯定取高的。
// Ⅱ. 不同代价肯定取便宜的，
// 因为：
// ① 便宜的高： 不解释。
// ② 二者同高： 不解释。
// ③ 便宜的矮： 它可以再花1变成无限高，
// 或者不花钱向后面的矮树转移。
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k,g;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&high[i]);
for(scanf("%d",&g);g--;)
{
scanf("%d",&k);
q[top=tail=1]=1;
for(i=2;i<=n;i++)
{
while(top<tail&&i-q[top]>k)top++;
f[i]=f[q[top]]+(high[i]>=high[q[top]]);
while(top<=tail&&cmp(high[i],f[i],high[q[tail]],f[q[tail]]))tail--;
q[++tail]=i;
}
printf("%d\n",f[n]);
}
return 0;
}
【BZOJ3831】【POI2014】Little Bird 单调队列，''再不刷它就土了''系列。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。