False0099 @ 2024-07-05 15:46:23
为什么这一题必须要在我们的单调队列里先加一个(0,0).如下所示:
deque<PII> dq;
dq.push_back({0,0});//为什么要加着一个?
for(int r=1;r<=n;r++){
int b=f[r-1]-s[r];
while(dq.size()&&dq.front().first<r-k){
dq.pop_front();
}
while(dq.size()&&dq.back().second<b){
dq.pop_back();
}
dq.push_back({r,b});
f[r]=max(f[r],dq.front().second+s[r]);
}
cout<<f[n]<<endl;
加了之后能AC,但是不加会wa on 4
deque<PII> dq;
for(int r=1;r<=n;r++){
int b=f[r-1]-s[r];
while(dq.size()&&dq.front().first<r-k){
dq.pop_front();
}
while(dq.size()&&dq.back().second<b){
dq.pop_back();
}
dq.push_back({r,b});
f[r]=max(f[r],dq.front().second+s[r]);
}
cout<<f[n]<<endl;
by D0000 @ 2024-07-18 20:58:44
b=f[r-1]-s[r];
中 -s[r]
就是用两个前缀和相减得到一段区间的和,但是注意,假设序列