首页 > 代码库 > 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