题解：P10977 Cut the Sequence

AWMMMMMM / 2024-11-09 / 原文

题目传送门

分析

看到这种题就可以想到动态规划，先设状态：$f_i$ 表示考虑前 $i$ 个数，所需要的最小代价。

发现 $f_i$ 可以从所有 $i$ 以前的状态加后一段区间转移过来，于是可以列出状态转移方程：

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

其中 $j$ 是上一个区间的右端点，$s$ 数组为前缀和数组。

不难发现每次转移 $f_i$ 的复杂度是 $O(N)$ 的，总复杂度为 $O(N^2)$，无法通过此题。

考虑将 $f_i$ 的转移过程进行优化。

由题目的性质，可以发现 $f_i$ 有单调不降的性质，基于这一点，我们可以在转移时：

如果 $a_j \leq a_{j+1}$。

则 $\max_{k = j}^i = \max_{k = j + 1}^i$。

则 $f_{j-1} + \max_{k = j}^i \leq f_j + \max_{k = j + 1}^i$。

基于这一点，可以转移过来的状态就可以用单调队列来存储了，并且用 multiset 来确定最优状态。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n, m, a[N], s[N], f[N], l, r, q[N << 2];
multiset<int> S;
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] > m) //如果有大于m的数，肯定无解，直接输出-1。
        {
            cout << -1;
            return 0;
        }
        s[i] = s[i - 1] + a[i];
    }
    l = 1;
    r = 0;
    for (int i = 1; i <= n; i++)
    {
        while (l <= r && s[i] - s[q[l]] > m) //如果当前区间和大于m，直接舍去。
        {
            S.erase(f[q[l]] + a[q[l + 1]]); //这里要加的是a[q[l+1]]，因为这是当前区间的最大值。
            l++;
        }
        while (l <= r && a[q[r]] < a[i]) //如果前面的数比当前数小，就会算错当前区间最大值，所以这里要提前弹出这些数。
        {
            S.erase(f[q[r - 1]] + a[q[r]]);
            r--;
        }
        if (l <= r) //如果弹完后，单调队列中还有元素，就可以加入以当前值作为最大值的答案。
        {
            S.insert(f[q[r]] + a[i]);
        }
        q[++r] = i;
        int L = 0, R = i - 1, c;
        while (L <= R) //这里求出距当前位置最远的区间左端点使区间的和小于等于m，为的是避免S中没有元素导致无法更新答案。
        {
            int mid = (L + R) >> 1;
            if (s[i] - s[mid] > m)
            {
                L = mid + 1;
            }
            else
            {
                c = mid;
                R = mid - 1;
            }
        }
        f[i] = f[c] + a[q[l]]; //这种情况下的最大值为a[q[l]]。
        if (S.size())
        {
            f[i] = min(f[i], *S.begin()); //如果S中有元素，就用S中最小的元素更新答案。
        }
    }
    cout << f[n];
}