题解：P10977 Cut the Sequence

· · 题解

题目传送门

分析

考虑本题解法，首先答案不具有单调性所以二分行不通（并不是所有的最大值最小化都可以用二分），且划分的区间数以及每段区间最大值出现的位置不易得知，故几乎无法使用贪心算法求解。发现如果只考虑最后一段划分的区间，那么其最值只与区间首尾有关，而与前面部分的划分无关，满足最优子结构的性质，考虑使用动态规划进行求解。

定义 f_i 表示划分完前 i 个数后每一部分的最大整数之和的最小值，以最后一段为划分依据，考虑转移：

f_i=\min_{0\le j<i\wedge \sum_{k=j+1}^ia_k\le m}(f_j+\max_{k=j+1}^ia_k)

发现 \max 求解时可以在扫描的时候用一个变量 O(1) 维护。所以 DP 的复杂度为 O(n^2)，此题无法通过，考虑优化。

我们可以尝试及时排除不必要的决策，首先考虑一个决策 j 何时可能成为最优决策。不难发现 f_i 呈现单调递增的趋势，即多加进来一个数，答案只会变大或者不变，否则可以用 f_i 的划分方式更新 f_{i-1} 使其减小。所以发现如果 j 从 i-1 向前枚举，若 \sum_{k=j+1}^ia_k\le m 条件满足且 \max_{k=j+1}^ia_k 不变的话（上界已经确定，所以最大值要么增大要么不变），那么答案将会变小，也就是说取前面的 j 一定更优，就可以排除很多决策了。

所以对于每一个 i，我们向前找到第一个满足 a_j>a_i 的 j，这个那么 j+1 到 i-1 的所有决策就都可以排除，而如果此时 j 不满足条件 \sum_{k=j+1}^ia_k\le m，那么我们向前找到第一个不满足条件的 j 作为决策，也就是把 j+1 到 i 这一段划分出来。手上有蓝书的同学就会发现我们利用单调性推导出了书中 j 需要至少满足一项的两个条件（而非先猜后证）：

所以我们可以利用单调队列维护所有可能成为最优解的决策点 j，即一个决策点 j 单调递增，数值 a_j 单调递减的队列。而 f_j+\max_{k=j+1}^ia_k 和 a_j 的单调性却没有关系，所以可以额外维护一个 multiset 来做到和单调队列一起删除，插入元素，每次取第一个迭代器就可以快速转移，时间复杂度 O(n\log n)。

代码实现

此题代码有很多细节，有些部分借鉴闫总代码，不好理解的结合代码一起看吧：

  1. 如何快速找到第一个不满足 \sum_{k=j+1}^ia_k\le m 的 j 呢，二分显然可以。但是双指针可以更快，因为 i 递增的时候 j 一定递增，所以我们用一个变量统计总和即可，并且每次及时删除单调队列中不符合的 j。
  3. 虽然每一个决策 j 都对应一个 f_j+\max_{k=j+1}^ia_k，但是根据第二条可知，每一项的最大值要依赖后一项，也就是说出了单调队列最后一项以外都可以求出对应的 f_j+\max_{k=j+1}^ia_k。而最后一项每次都由新插入的 i 来更新即没插入 i 前的最后一项在插入 i 后就变成了倒数第二项可以更新。而此时有人会疑惑 i 又无法更新，但是这样的担心是不必要的，因为 i 无法更新 f_i，而下一轮中若 i 还存在在单调队列中则会以相同的方式来更新。同理删除元素时第一次删除的即队尾不更新 multiset。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+100;
int n,a[N],l=1,r,q[N];
ll m,dp[N],sum;
multiset<ll> st;

void shan(ll x)
{
    if(st.find(x)==st.end()) return;//相当于是在这里判断元素存不存在了
    st.erase(st.find(x));
}

int main()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>m)//不合法的情况
        {
            printf("-1\n");
            return 0;
        }
    }
    for(int i=1,j=0;i<=n;i++)//j就是第一个不满足和小于等于m的位置，详见1
    {
        sum+=a[i];//j+1到i这一段的和
        while(sum>m) sum-=a[++j];
        while(l<=r&&q[l]<j) shan(dp[q[l]]+a[q[l+1]]),l++;//及时排除不合法的决策
        while(l<=r&&a[q[r]]<=a[i]) shan(dp[q[r-1]]+a[q[r]]),r--;//不满足单调性，这里用r-1就是因为最后一项不删，详见3
        if(l<=r) st.insert(dp[q[r]]+a[i]);//队尾用i来更新，详见3
        q[++r]=i;
        dp[i]=dp[j]+a[q[l]];//可能的决策2
        if(st.size()) dp[i]=min(dp[i],*st.begin());//可能的决策1
    }
    printf("%lld\n",dp[n]);
    return 0;
}

完结撒花！！！