Reinforced Problem

题目描述

原神是一款开放世界的动作角色扮演游戏，玩家一次可以选择四名角色参与战斗，并且在战斗中可以快速切换。角色可以通过各种方式增强他们的力量，例如提高角色的等级，改进角色装备的圣遗物和武器。

zml 就是一名忠实的原神玩家，但是由于 ffg 对原神的强烈抵制，zml 不得不规划一下自己玩原神的时间。

zml 第 $i$ 天玩原神都会有一个喜悦值 $a_i$，与此同时，ffg 也会在这天有一个对原神玩家的愤怒值 $b_i$，并且假如 zml 连续几天玩原神这个愤怒值会累加，假如有一天没有玩原神，ffg 就会原谅他，然后愤怒值清空，但是 zml 的喜悦值不会受到影响。

ffg 有个忍耐值 $m$，只要 ffg 的愤怒值没有超过 $m$，ffg 就不会爆发，zml 就可以安然无恙的玩原神，否则 ffg 就会把他炖了。

现在基于 zml 每天的喜悦值和 ffg 对原神玩家的愤怒值，请你输出 zml 的最大喜悦值（当然，zml 不想被炖）。

输入描述: 

第一行包含一个整数 $T(1 \leq T \leq 10^4)$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n,m(1 \leq n \leq 10^5, 0 \leq m \leq 10^{14})$，$n$ 表示天数，$m$ 表示 ffg 的最大愤怒值。

第二行包含 $n$ 个数 $a_1, a_2, \ldots, a_n (1 \leq |a_i| \leq 10^9)$，表示 zml 在第 $i$ 天的喜悦值 $a_i$。

第三行包含 $n$ 个数 $b_1, b_2, \ldots ,b_n (1 \leq |b_i| \leq 10^9)$，表示 ffg 在第 $i$ 天的愤怒值 $b_i$。

保证所有测试用例的 $n$ 加起来的和不超过 $2 \times 10^5$。

输出描述:

对于每个测试用例，输出一个整数，表示 zml 玩原神的最大喜悦值（不被邪恶的 ffg 炖的前提下）。

示例1

输入

1
4 6
8 4 3 1
5 2 -2 2

输出

12

说明

对于样例 $1$，zml 会选择第 $1$ 天，第 $3$ 天和第 $4$ 天

- 第 $1$ 天 ffg 的愤怒值为 $5$， zml 的喜悦值为 $8$。

- 第 $2$ 天由于 zml 不选择玩原神，所以 ffg 的愤怒值降为 $0$，zml 的喜悦值仍然为 $8$。

- 第 $3$ 天 ffg 的愤怒值为 $−2$，zml 的喜悦值为 $11$。

- 第 $4$ 天 ffg 的愤怒值为 $−1$，zml 的喜悦值为 $13$。

为什么 zml 不选择第 $1$ 天，第 $2$ 天和第 $3$ 天呢？这连续 $3$ 天的愤怒值之和是 $5$。 这是因为假如选择第 $1$ 天，第 $2$ 天和第 $3$ 天，ffg 在第 $2$ 天愤怒值为 $7$，ffg 就会把 zml 炖了，也就是说，假如 ffg 的愤怒值中途大于 $m$，即使后面降下来了也无济于事。

示例2

输入

5
6 9
2 4 3 1 5 1
9 1 1 1 -4 2
5 16
8 7 8 4 -1
1 6 6 7 9
5 7
1 1 -1 -2 8
7 -5 9 3 1
6 6
5 8 -2 8 5 -4
7 -5 5 1 5 -2
4 15
-3 3 5 8
-3 10 7 -3

输出

14
23
10
21
13

解题思路

  本质上就是选出若干个互不相交的区间，使得这些区间的 $a_i$ 总和最大。其中对于每个区间 $[l_i, r_i]$ 要满足 $r_{i-1}+1 < l_i$（否则第 $i-1$ 个区间与第 $i$ 个区间可以合并成一个区间），且每个区间关于 $b_i$ 的任意一个前缀的和不可以超过 $m$，即 $\sum\limits_{j=l_i}^{k}{b_j} \leq m, \, k \in [l_i, r_i]$。

  考虑 dp，定义 $f(i)$ 表示从前 $i$ 天选出的所有合法区间中喜悦值的最大值，根据是否以第 $i$ 天作为区间的右端点进行状态转移。状态转移方程为

$$f(i) = \max\left\{f(i-1), \, \max\limits_{j \in S}\left\{f(j-1) + sa_{i} - sa_{j}\right\}\right\}$$

  其中 $sa_i = \sum\limits_{j=1}^{i}{a_j}$，$S$ 表示满足以下要求的下标 $j$ 的集合：

• $0 \leq j < i$。
• 定义 $sb_i = \sum\limits_{j=1}^{i}{b_j}$，则 $\forall k \in [j+1, i]$，$sb_k - sb_{j} \leq m$。

  显然直接暴力转移的话时间复杂度是 $O(n^3)$ 的。如果 $j$ 满足条件，那么对于每个 $k \in [j+1,i]$ 对应的  $sb_k \leq sb_j + m$。因此我们可以先通过 RMQ 维护关于 $sb_i$ 的区间最大值，在枚举 $j$ 时，如果区间 $[j+1,i]$ 内的 $sb_k$ 的最大值不超过 $sb_j + m$，那么就可以从 $j$ 处转移过来，这样时间复杂度就降到了 $O(n^2)$。

  如果要优化到 $O(n)$ 意味着不能枚举 $j$ 了。反过来思考，对于每个 $j$ 如果以 $j+1$ 作为区间的左端点，能不能求出右端点最远可以到达哪里？这是可以的，我们可以二分出这个右端点，对于二分点 $\text{mid}$，check 的时候只需判断区间 $[j+1, \text{mid}]$ 内的 $sb_k$ 的最大值是否不超过 $sb_j + m$。不过在代码实现中，二分出来的是不满足条件的最小位置，也就是最远合法右端点的下一个位置（不存在则设为 $n+1$）。

  这样在从小到大枚举 $i$ 时，开一个 `std::multiset` 集合维护 $j \in [0,i-1]$ 关于 $f(j-1) - sa_j$ 的最大值。对于合法右端点小于 $i$ 的位置 $j$，需要将 $f(j-1)-sa_j$ 从集合中删掉。设当前集合中的最大值为 $x$，则 $f(i) = \max\{f(i-1), x + sa_i\}$。

  AC 代码如下，时间复杂度为 $O(n \log{n})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

LL sa[N], sb[N];
LL g[18][N];
vector<int> p[N];
LL f[N];

LL query(int l, int r) {
    int t = __lg(r - l + 1);
    return max(g[t][l], g[t][r - (1 << t) + 1]);
}

void solve() {
    int n;
    LL m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> sa[i];
        sa[i] += sa[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        cin >> sb[i];
        sb[i] += sb[i - 1];
    }
    sb[n + 1] = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; 1 << i <= n + 1; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n + 1; j++) {
            if (!i) g[i][j] = sb[j];
            else g[i][j] = max(g[i - 1][j], g[i - 1][j + (1 << i - 1)]);
        }
    }
    for (int i = 1; i <= n + 1; i++) {
        p[i].clear();
    }
    for (int i = 0; i < n; i++) {
        int l = i + 1, r = n + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (query(i + 1, mid) > sb[i] + m) r = mid;
            else l = mid + 1;
        }
        p[l].push_back(i);
    }
    multiset<LL> st;
    for (int i = 1; i <= n; i++) {
        st.insert(f[max(0, i - 2)] - sa[i - 1]);
        for (auto &x : p[i]) {
            st.erase(st.find(f[max(0, x - 1)] - sa[x]));
        }
        f[i] = f[i - 1];
        if (!st.empty()) f[i] = max(f[i], *st.rbegin() + sa[i]);
    }
    cout << f[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

参考资料

  题解 | #环形取数#_牛客博客：httpsblog.nowcoder.netn0aad26a6e07e4e49a85c058b878cc03e