[BZOJ 3831]Little Bird

danihao123 posted @ 2016年8月12日 20:23 in 题解 with tags 动态规划 递推 单调队列 POI bzoj , 868 阅读
转载请注明出处:http://danihao123.is-programmer.com/

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划,然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可,递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响,也不过是1,这样撑死也不会使答案更差

但凡是单调队列的题,都会有神秘细节,这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码:

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}
JIO Switch 说:
Dec 19, 2022 08:09:04 PM

Jio Switch is created. A simple interface and the absence of advertisements are two positive aspects of the Jio application for India. However, the product does not include a cloud-based or on-premises alternative. JIO Switch JioSwitch, however, allows users to transfer or request large files with others and is quite simple to install and administer.

Bharat Fiber 说:
Feb 08, 2023 04:24:15 PM

BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs. Bharat Fiber Telecom Infrastructure Providers (TIPs) with new BSNL Fiber plans covering many isolated pockets in all BSNL circles of the country for 50Mbps to 300 Mbps internet speed on providing with BSNL Fiber Plans along with FREE ONT as per the possibility.

booksyllabus.com 说:
Jul 03, 2023 11:28:10 AM

Initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country.Our team comprises of professional writers & citizen booksyllabus.com journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest.Our reporting team intends to publish the Education & Recruitment Update for all age groups and present the true picture of the recent events with the inside coverage.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter