破案了 这题用deque define int long long必寄
by _Remake_ @ 2023-02-09 11:10:26
我代码只用一个deque。O2能过。
by LHQing @ 2023-02-09 11:10:52
long long拉了。/qd
by LHQing @ 2023-02-09 11:11:05
lhq咋啥题都做过/qd/qd
by _•́へ•́╬_ @ 2023-02-09 11:16:56
lhq tql
by __11jiang08__ @ 2023-02-09 11:20:57
你说得对，但是我们这个 deque 体积小方便携带，拆开一包，放评测机里就变大，怎么放都放不下，用来打 CSP，打 NOIP ，打 NOI 都是很好用的，你看打开以后像 1KB 一样大小，放在评测机里变大变高，占空间很大的。打开以后，是一个加大加长的双端队列，你看他怎么开都开不下，使用 1e6 次都没问题，出差打比赛带上它非常方便。
什么？在哪里买？下方 @NOI2022 D1T1 出题人 ，买 1GB 送一块铁牌，还包邮。
by zhy137036 @ 2023-02-09 11:26:55
我这个deque也不是过了
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[1000010],f[1000010];
deque<int> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m,k;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
while(m--){
cin>>k;
memset(f,63,sizeof(f));
q.clear();
f[1]=0;
q.push_back(1);
for(int i=2;i<=n;i++){
while(!q.empty()&&q.front()<i-k) q.pop_front();
if(!q.empty()) f[i]=min(f[i],f[q.front()]+(a[i]>=a[q.front()]));
while(!q.empty()&&f[i]<f[q.back()]) q.pop_back();
while(!q.empty()&&f[i]==f[q.back()]&&a[i]>=a[q.back()]) q.pop_back();
q.push_back(i);
}
cout<<f[n]<<endl;
}
return 0;
}
```
by zhujianheng @ 2023-07-24 23:18:46