题解：P10977 Cut the Sequence

CJZJC · 2024-09-25 18:04:39 · 题解

题目传送门

分析

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

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

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

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

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

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

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

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

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

基于这一点，可以转移过来的状态就可以用单调队列来存储了，并且用 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];
}

小结

这种题目比较简单，其实通过挖掘题目性质就可以做出来，希望读者以后再做类似的题时也能做出来。