首页 > 代码库 > BZOJ 3831 POI 2014 Little Bird 单调队列DP
BZOJ 3831 POI 2014 Little Bird 单调队列DP
题目大意:给出一片树林,树排成一排,每一棵树都有一个高度。从地一棵树出发,每次可以跳到i+k棵之前,跳到小于自己高度的树上不需要花费体力,反之需要花费一点体力,问到最后一棵树最少需要多少体力。
思路:简单DP方程:f[i] = min{f[j] + (height[i] >= height[j])}
然后发现数据范围只有O(n)可以过。
维护单调队列,队列中按照f单调递减,队尾按照时间往出弹。
当f值相同的时候,高度较高的优先。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 using namespace std; int cnt,src[MAX]; int f[MAX]; int asks,k; struct Complex{ int pos,height,x; Complex(int _,int __,int ___):x(_),height(__),pos(___) {} Complex() {} }; deque<Complex> q; int main() { cin >> cnt; for(int i = 1; i <= cnt; ++i) scanf("%d",&src[i]); cin >> asks; for(int i = 1; i <= asks; ++i) { scanf("%d",&k); f[0] = 0; while(!q.empty()) q.pop_front(); q.push_back(Complex(1,src[1],0)); for(int j = 2; j <= cnt; ++j) { while(!q.empty() && j - q.front().pos > k) q.pop_front(); while(!q.empty() && (q.back().x > f[j - 1] || (q.back().x == f[j - 1] && q.back().height <= src[j - 1]))) q.pop_back(); q.push_back(Complex(f[j - 1],src[j - 1],j - 1)); f[j] = q.front().x + (src[j] >= q.front().height); } printf("%d\n",f[cnt]); } return 0; }
BZOJ 3831 POI 2014 Little Bird 单调队列DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。