P3572 [POI 2014] PTA-Little Bird——简单的单调队列
li_cat
·
·
个人记录
初见思路
注意到 $q$ 很小，直接每一个都跑一遍 $dp$ 是可行的
设 $dp_i$ 为到第 $i$ 棵树时的最小劳累值，易得
$$dp_i=min_{i-k\le j<i}(dp_j+[d_j<=d_i])$$
时间复杂度 $O(qnk)$ ，肯定过不了
### 走歪了的线段树
可以看到**有一个大小为 $k$ 的滑动窗口，可以尝试单调队列优化**
但是转移的过程中要用到对应状态的 $d$ ，所以考虑分类讨论
如果按照大小分类讨论，并且这个作为标准的量会不断变化的话，类似**权值线段树**的方法是很合适的
注意到虽然 $d$ 的值域很大，但是数量只有 $n$ 级别
考虑离散化，再针对每一个 $d$ 开一个单调队列，在离散化后的值域这一维上建一棵线段树，维护对应区间的最小值
这样就可以进行愉快的 $dp$ 了
时间复杂度 $O(qn\log n)$ ，非常危险（事实上就是没过）
### 正统的单调队列
认真想一想， $d$ 的大小关系对答案的影响**并没有那么大**（此处专门指**单调性**）
如果从 $dp$ 值各不同的位置中选择一个位置转移，那么 $dp$ 值最小的**一定是最优解之一**
因为如果从非最小的 $dp$ 值切换到最小的 $dp$ 值，答案**一定不会变劣**，这是因为就算 $dp$ 值只减小了 $1$ ，也能弥补高度的劣势
所以，当需要转移的时候，最优的选择**一定在 $dp$ 值最小的那一批里**
此时，这些状态中当然是高度越高越好，因为越高越有可能去掉 $1$ 的代价变为最优
所以，可以考虑将这些带有高度和 $dp$ 值的节点丢进单调队列里，其中越靠前的节点：
- $dp$ 值更小
- 高度更高
优先保证第一点
最后，我们试一试变换不同的高度，会发现队列内**永远是单调的**，因为对于一个节点，就算前面的同 $dp$ 值的部分都减少了 $1$ 的代价，也能和前面更优的 $dp$ 值接起来形成单调递减的结构
时间复杂度 $O(nq)$ ，很稳
### AC Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int inf=0x3f3f3f3f;
struct node{
int val,h;
bool operator<(node y){
if(val==y.val) return h>y.h;
return val<y.val;
}bool operator==(node y){
return (val==y.val&&h==y.h);
}
};
struct ddqueue{
list<node> q;
void push(node x){
while(!q.empty() && x<q.back()) q.pop_back();
q.push_back(x);
}void pop(node x){
if(q.empty()) return ;
if(q.front()==x) q.pop_front();
}int query(int h){
if(q.empty()) return inf;
return q.front().val+(q.front().h<=h);
}//
}q;
int dp[MAXN],d[MAXN],n,m;
void getdp(int k){
q.q.clear();
dp[1]=0;q.push(node{0,d[1]});
for(int i=2;i<=k;++i){
dp[i]=q.query(d[i]);
q.push(node{dp[i],d[i]});
}for(int i=k+1;i<=n;++i){
dp[i]=q.query(d[i]);
q.push(node{dp[i],d[i]});
q.pop(node{dp[i-k],d[i-k]});
}
printf("%d\n",dp[n]);
}//
void work(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&d[i]);
scanf("%d",&m);
for(int i=1,k;i<=m;++i){
scanf("%d",&k);
getdp(k);
}
}//
int main(){
work();
return 0;
}
```