STL单调队列求助

P2627 [USACO11OPEN] Mowing the Lawn G

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] 就是用两个前缀和相减得到一段区间的和,但是注意,假设序列 A_ii 位前缀和是 S_i,那么 A_lA_r 的和是 S_r-S_{l-1},考虑 l=0,需要用到 S_0=0


|