[BZOJ 3831]Little Bird
单调队列水体……然而我这蒟蒻仍然WA一墙
这个题本质是一个动态规划，然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……
优先级直接按照递推值来搞即可，递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响，也不过是1，这样撑死也不会使答案更差
但凡是单调队列的题，都会有神秘细节，这题也不例外……顺便说一下这题不要傻乎乎的用pair
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | /************************************************************** 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;} |
[BZOJ 2442]修剪草坪
单调队列优化DP……
bi了doge了……现在才能学会一些简单的单调队列优化DP
代码：
