Code 備忘錄►DP

TIOJ::1841-好．傳囉！ Nice Boat！

http://tioj.ck.tp.edu.tw/problems/1841
POI轉到TIOJ的題目，很有趣的單調隊列題。
很久以前寫的，所以花了一些時間回想。

這題是從 POI 21th 第一題沙拉吧(Salad Bar)稍微做些修改而來的。

題目是給你一個整數序列，問你最長的安全區間長度是多少。
所謂的安全區間就是所有的前綴和和後綴和都大於等於0。

這題可以很容易的往把序列轉成前綴和去想。
轉成前綴和之後，我們可以發現，我們想要找的區間，就是這個區間滿足，區間的起點是區間最小值，區間的終點是區間最大值。
因為只要起點是最小值，那區間中每個點減起點都大於等於零，也就是這個區間內的每個前綴和都大於等於零；同理終點是最大值就代表終點減每個點都大於等於0，也就是這個區間內的每個後綴和都大於等於零。

那我們怎麼找到這個區間呢？
我們可以 $O(N^2)$ 的去尋找，對於每個左界，我們找找看他的右界最遠可以到哪裡。
這樣一找我們就發現，這個右界不可能超過第一個比左界小的位置，不然左界就不是區間最小值了。
同時，我們找右界的時候，因為右界是區間最大值，當我們要找下一個位置時，除非下一個位置的值大於等於這個位置的值，不然我們不用去考慮他，也就是我們只要找到右邊比現在這個點高(或一樣高)的位置就好了，中間的東西不用理他。
於是我們可以綜合以上兩點，維護兩個單調隊列 $ L(i), R(i) $，分別代表右邊第一個小於 i 位置的位置和右邊第一個大於等於 i 位置的位置。
找答案時就維護兩個指針 l 和 r ，分別指向左界和右界，一開始都初始化成0。接著我們就要在 $[l, L(l) )$ 之間找答案(左界和右邊第一個小於左界的位置)。我們可以線性掃過去，找到最大值就是我們要的右界。直接做會太慢，於是我們可以用跳躍的，也就是直接看 $R(r)$ (右邊第一個比現在的位置大或一樣大的位置) 是不是還在我們限制的區間 $[l, L(l) )$ 內，如果是的話就跳過去。

這樣每次 r 不能再往右跳時，我們就找到一個合法區間，直接取 max 紀錄答案。
接下來，因為我們確定下一個左界不可能在現在的右界的左邊，因為區間內的所有點都大於等於原左界，所以 $L(l)$ 不會向右，右界也就不可能向右，所以左界在原右界左邊的區間全部都小於等於剛才的答案，可以直接跳過。所以我們可以直接做 $l = r = r+1$ ，也就是直接從右界的下一個位置開始找其他可能的答案。
因為上述的保證，我們可以發現 l 和 r 都是遞增的，所以這樣的作法是線性的。

實作時，可以把最後還留在單調隊列裡的點直接設定成 N+1 (N 為序列長度)，這樣在寫法上就會很漂亮。

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
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 1000010
#define LL long long
using namespace std;
LL ST[N],SUM[N];
int t,l,r,ans,n,st,R[N],L[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        F(n){
            cin>>SUM[i+1];
            SUM[i+1]+=SUM[i];
        }
        st=0;
        F(n+1){
            while(st&&SUM[ST[st-1]]<=SUM[i])R[ST[--st]]=i;
            ST[st++]=i;
        }
        while(st--)R[ST[st]]=n+1;
        st=0;
        F(n+1){
            while(st&&SUM[ST[st-1]]>SUM[i])L[ST[--st]]=i;
            ST[st++]=i;
        }
        while(st--)L[ST[st]]=n+1;
        l=r=ans=0;
        while(l<n){
            while(r<=n&&R[r]<L[l])r=R[r];
            ans=max(ans,r-l);
            l=r=r+1;
        }
        cout<<ans<<'\n';
    }   
}