[POJ 3017]Cut the Sequence

說明：
$S_{i}$為序列的第$i$個元素
$\max(a,b)=\max_{i=a}^{b}S_{i}$
$k_{i}$為滿足$\sum_{j=k}^{i}S_{j}\leq M$最小的$k$

我們可以構造一個$DP$，$DP[i]$代表把前$i$個元素組成了序列切一切，各段最大值總和的最小值
初始條件：$DP[0]=0$

於是，我們有了$DP[i]=\min(DP[k-1]+\max(k,i))$，其中$k_{i}\leq k\leq i$

如果有做過單調隊列的題目，相信很容易在將$i$從小到大枚舉的時候，均攤$O(1)$維護所有的$max(k,i)$，以及$k_{i}$

直接依照單調隊列裡面的元素去枚舉是$O(N^{2})$，也就是網路上宣稱不用set或平衡樹直接單調隊列解決的做法

例如這篇

我構了測資讓它跑了一分鐘還沒出來，所以請別偷懶，繼續看怎麼優化

這個測資是：

100000 9223372036854775807

100000 99999 99998 99997 ...... 5 4 3 2 1

怎麼優化呢？

可以發現，當$i$遞增時，$DP[i]$是非遞減的

因此，如果現在$i$跑到$9$，並算出$k_{9}=3$，單調隊列是$\{5,6,9\}$

那麼$DP[i]$的候選人就是$DP[2]+S_{5}$、$DP[5]+S_{6}$、$DP[6]+S_{9}$

除了第一個候選人，其他的如果用multiset存起來，在單調隊列執行pop_front、pop_back、push_back操作的時候就可以順便$O(\log N)$維護這些候選人了
為了確認你的理解，這些候選人的數量永遠是「單調隊列的大小-1」

因此，要算$DP[i]$時，只要取multiset裡面的最小值，和區間取$[k_{i},i]$時的花費 (也就是上述例子的第一個候選人)，這兩個的最小值就好了

時間複雜度：$O(N\log N)$

code:

#include<cstdio>
//#include<cassert>
#include<set>
#include<algorithm>
using namespace std;
void assert(bool valid){if(valid)return;for(int a=0,b=0;;)a/=b;}
typedef long long LL;
struct Deq
{
    int s[100001],l,r;
    void clear(){l=0,r=-1;}
    void push_back(const int v){s[++r]=v;}
    void pop_back(){r--;}
    void pop_front(){l++;}
    int back(const int i)const{return s[r-i];}
    int front(const int i)const{return s[l+i];}
    int size()const{return r-l+1;}
    bool empty()const{return r<l;}
//    void Print()const{for(int i=l;i<=r;i++)printf("%d ",s[i]);puts("");}
}DEQ;
int N,S[100001];
LL M,SUM[100001],DP[100001];
multiset<LL>BEST;
void Erase(const LL &v)
{
    multiset<LL>::iterator it=BEST.find(v);
    assert(it!=BEST.end());
    BEST.erase(it);
}
void PopFront()
{
    if(DEQ.size()>=2)Erase(DP[DEQ.front(0)]+S[DEQ.front(1)]);
    DEQ.pop_front();
}
void PopBack()
{
    if(DEQ.size()>=2)Erase(DP[DEQ.back(1)]+S[DEQ.back(0)]);
    DEQ.pop_back();
}
void PushBack(const int i)
{
    DEQ.push_back(i);
    if(DEQ.size()>=2)BEST.insert(DP[DEQ.back(1)]+S[DEQ.back(0)]);
}
LL Solve()
{
    for(int i=1;i<=N;i++)if(S[i]>M)return -1LL;
    DEQ.clear(),DEQ.push_back(0),BEST.clear();
    DP[0]=S[0]=0;
    for(int i=1,l=0;i<=N;i++)
    {
        while(!DEQ.empty()&&S[i]>=S[DEQ.back(0)])PopBack();
        PushBack(i);
        while(!DEQ.empty()&&SUM[i]-SUM[DEQ.front(0)-1]>M)PopFront();
        while(SUM[i]-SUM[l]>M)l++;
        assert(!DEQ.empty());
        assert(l<i);
        DP[i]=DP[l]+S[DEQ.front(0)];
        if(!BEST.empty()&&*BEST.begin()<DP[i])DP[i]=*BEST.begin();
        assert(DP[i]>=DP[i-1]);
//        printf("DP[%d]=%lld\n",i,DP[i]);
//        DEQ.Print();
    }
    return DP[N];
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%lld",&N,&M)==2)
    {
        SUM[0]=0LL;
        for(int i=1;i<=N;i++)scanf("%d",&S[i]),SUM[i]=SUM[i-1]+S[i];
        printf("%lld\n",Solve());
    }
    return 0;
}