[POJ 3017][DP] Cut The Sequence

原題連結
嗚姆
個人頗喜歡這道題，大概是因為我做了蠻久的(?

令dp[i]代表以位置i結尾的序列所需的總代價，容易列出轉移方程
dp[i]= min {dp[j] + max( a[j] , a[j+1] , ...... , a[i]) } , L<=j<=i
其中L是最小的位置使得pre[i]-pre[L-1]<=M (pre:前綴和)

那麼，直接照定義做是O(n^2)，顯然是要TLE的
觀察一下轉移函數，重點在於max函數的性質(這可以從其他序列問題的單調性上獲得經驗)。
舉例說明比較快：

假設一序列
2 6 3 4 5 1

如果我們在位置5，按照一般的枚舉方法，讓j從5遞減到1時，我們遇到的最大值應該是這樣：
6 6 4 4 5

也就是枚舉的過程中，每一個有出現的最大值會形成一段連續的區間。

還有一個顯而易見的事實：dp[i]應該隨著i非嚴格遞增，BJ4。
根據這兩個性質，我們很容易發現，在同一段區間中，我們會盡量選擇靠左的位置來更新，因為比較右邊的答案不會更好。

所以就可以聯想到普通的單調隊列，枚舉i的過程中把deque尾端所有比i小的元素一個個刪掉，然後看情況把deque首端的元素pop掉。(別忘了還有總和<M的約束條件)

就算有了一個單調的deque可以維護決策點，最差的狀況下deque裡還是會保持O(n)個點耶！(例如整個序列遞減的情況)
那麼也不能直接枚舉deque裡的點，到底要怎麼快速求出dp[i]呢？

這邊我也是想了很久...答案意外的非常簡單。
因為dp[i]的轉移式裡關於max的部份我們已經透過deque處理好了，剩下的部份又只跟j有關，所以可以用set(or any BST)去動態維護最小值，只要deque在push和pop時好好insert跟erase，答案就會是好的。

剩下的細節就參考code吧。

#include<cstdio>
#include<deque>
#include<algorithm>
#include<set>
#define LL long long
using namespace std;
const LL maxn=100000+5;
LL a[maxn],dp[maxn],pre[maxn];
struct P
{
    LL p,id;
    P(LL a,LL b):p(a),id(b) {}
    LL getVal()const {return dp[p]+a[id];}
    bool operator < (const P &rhs) const {return getVal()<rhs.getVal();}
};
set<P> S;
deque<P> dq;
int main()
{
    LL N,M,i;
    scanf("%lld%lld",&N,&M);
    pre[0]=dp[0]=0;
    for(i=1;i<=N;i++) {scanf("%lld",a+i);pre[i]=pre[i-1]+a[i];}
    LL L=1;
    for(i=1;i<=N;i++)
    {
        while(pre[i]-pre[L-1]>M) L++;
        if(L>i) break;
        while(dq.size() && dq.front().p+1<L)
        {
            S.erase(dq.front());
            if(dq.front().id>=L)
            {
                dq.front().p=L-1;
                S.insert(dq.front());
            }
            else dq.pop_front();
        }
        while(dq.size() && a[i]>a[dq.back().id]) {S.erase(dq.back());dq.pop_back();}
        P topush=P(dq.size()?dq.back().id:L-1,i);
        S.insert(topush);dq.push_back(topush);
        dp[i]=(*S.begin()).getVal();
    }
    printf("%lld\n",L>i?-1:dp[N]);
}