Cut the Sequence

Cut the Sequence

有一个长度为n的序列\(\{a_i\}\)，现在求将其划分成若干个区间，并保证每个区间的和不超过m的情况下，每个区间的最大值的和的最小值，\(0 < N ≤ 100 000\)。

解

不难想到，设\(f_i\)表示把前i个位置划分后的所求，设s为a的前缀和，于是有

\[f_i=\min_{j=0,s_i-s_j\leq m}^{i-1}\{f_j+\max_{k=j+1}^i\{a_k\}\}\]

关键在于这是\(O(n^2)\)递推，于是有以下结论优化

• f具有单调性

把得到\(f_i\)的方案中，去除掉第i个位置变为\(f_{i-1}\)，要么不变，要么变小，而此时得到\(f_{i-1}\leq f_i\)，于是得证。

• 最优决策点j一定满足以下条件之一

1. \(\max_{k=j}^i\{a_k\}=a_j\)（即\(a_j\)大于等于\(a_{j+1},...,a_i\)）
2. \(s_i-s_{j-1}>m\)(即j是最小的j使\(s_i-s_j\leq m\))

假设最优决策点j都不满足，必然有\(a_j\leq \max_{k=j+1}^i\{a_i\}\),也即
\(\max_{k=j}^i\{a_i\}=\max_{k=j+1}^i\{a_i\}\),而\(s_{i}-s_{j-1}\leq m\)意味着j-1是一个决策点，于是我们有

\(f_{j-1}+\max_{k=j}^i\{a_i\}\leq f_j+\max_{k=j+1}^i\{a_i\}\)

于是我们得知会有决策点j-1比j更优，因此矛盾，故得证。

因此对于即j是最小的j使\(s_i-s_j\leq m\)，我们假设在第i-1个位置的j已经维护出来，而考虑第i个位置，此时多加了一个\(a_i\),如果不能满足条件，只要往后拉即可，这样可以做到\(O(n)\)。

至于\(a_j\)大于等于\(a_{j+1},...,a_i\)，故如果转移到求\(f_{i+1}\)，多了一个\(a_{i+1}\),如果\(a_{i+1}>a_j\)，必然它就不再满足了，于是可以去除，而\(s_{i}-s_{j}\)又是一个单调的函数，于是我们可以维护单调递减的单调队列维护决策点a的单调性，并保证s的不超过范围。

现在问题在于如何快速求出决策点转移过来的值，易知对于决策点j\(f_j\)已是确定了，因为单调队列的性质，容易知道，决策点j的\(\max_{k=j+1}^i\{a_k\}\)也就是j在单调队列中的位置的下一个位置的a，根据这一性质，注意对单调队列末尾的特判即可。

参考代码：

#include <iostream>
#include <cstdio>
#include <deque>
#include <set>
#define il inline
#define ri register
#define ll long long
using namespace std;
int D[100005],H(1),T(0);
multiset<ll>S;
int a[100005];
ll dp[100005],m,sum;
template<class free>
il void read(free&);
template<class free>
il free Min(free,free);
int main(){
    int n;read(n),read(m);
    for(int i(1);i<=n;++i)read(a[i]),dp[i]=1e10;
    for(int i(1),t(1);i<=n;++i){
        sum+=a[i];while(sum>m)sum-=a[t++];
        while(H<=T&&D[H]<t)
            S.erase(S.find(dp[D[H]]+a[D[H+1]])),++H;
        while(H<=T&&a[D[T]]<a[i])
            S.erase(S.find(dp[D[T]]+a[D[T+1]])),--T;
        if(H<=T&&D[T]!=i-1)
            S.erase(S.find(dp[D[T]]+a[D[T+1]])),
                S.insert(dp[D[T]]+a[i]);
        if(H<=T)dp[i]=Min(dp[t-1]+a[D[H]],*S.begin());
        else dp[i]=dp[t-1]+a[i];
        D[++T]=i,S.insert(dp[i]+a[i+1]),D[T+1]=i+1;
    }if(dp[n]<1e10)printf("%lld",dp[n]);
    else puts("-1");
    return 0;
}
template<class free>
il free Min(free a,free b){
    return a<b?a:b;
}
template<class free>
il void read(free &x){
    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

Cut the Sequence

原文：https://www.cnblogs.com/a1b3c7d9/p/10962007.html