原题呈现

P10381 杂赛选比#

题目背景#

你说得对，但是小 $\iiint$ 在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子，痛失 2h 遗憾离场，希望大家引以为戒．

题目描述#

给定一个长度为 $n$ 的数组 $a$ ，初始只有 $a_1$ 是已被解锁的．现在有一个整数 $i$ ，初始值为 $1$ ．现在小 $\iiint$ 在对这个数组进行一个游戏：

如果 $a_i$ 未被解锁，游戏结束．
否则他可以将 $a_{i+1\sim i+a_i}$ 设置成已被解锁的，或是获得 $a_i$ 个金币（如果 $a_i=0$ 则无法解锁任何元素），然后将 $i$ 加 $1$ ．

请你求出游戏结束后你能获得的最大金币数量．

输入格式#

本题有多组测试数据．

第一行一个整数 $T$ ，表示测试数据组数．

对于每一组数据，第一行一个正整数 $n$ ．

接下来一行 $n$ 个非负整数 $a_{1\sim n}$ ．

输出格式#

对于每一组数据，一行一个数，表示答案．

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

1
1
2
10
3
1 1 4 5 1 4 1 9 1 9

输出 #2#

1
26

说明/提示#

【样例 1 解释】#

对于第一组数据，你可以解锁 $a_2$ ，再获得 $a_2$ 个金币．而对于第三组数据，你无法解锁 $a_2$ ，因此只能获得 $0$ 个金币．

对于第二组数据，你可以解锁 $a_2,a_3$ ，并获得 $9$ 个金币．

【样例 2 解释】#

将第 $1,2,3,6$ 个位置用于解锁为最优方案．

【数据范围】#

对于 $100\%$ 的数据， $1\le n\le10^5$ ， $0\le a_i\le10^5$ ， $T\le 5$ ．

测试点编号	$n\leq$	$a_i\leq$	$T=$	特殊性质
$1$	$10$	$0$	$1$	/
$2\sim3$	$10$	$5$	$1$	/
$4\sim5$	$600$	$600$	$1$	/
$6\sim8$	$5000$	$5000$	$1$	/
$9\sim10$	$10^5$	$5$	$5$	/
$11\sim12$	$5\times10^4$	$10^5$	$5$	$a_i>n$
$13\sim20$	$10^5$	$10^5$	$5$	/

此题考虑使用动态规划．

不妨定义 dp[i][0/1] 表示考虑到第 $i$ 张卡牌（即 $a$ 数组中第 $i$ 个数），且第 $i$ 张选择用于解锁（第二维为 0）或选择用于获得金币（第二维为 1），所能够获得的最大金币．

显然，当想要去考虑第 $i$ 张卡牌，前提是第 $i$ 张卡牌被解锁．因此，dp[i][0/1] 可以由所有能够解锁第 $i$ 张卡牌的状态转移而来．具体来说，是由所有满足以下条件的卡牌 $j$ 从 dp[k][0] 转移而来：

卡牌 $j$ 的解锁范围能够触及到卡牌 $i$ ，即 $j + a[j] \geq i$ ．

由于使用卡牌 $j$ 之后，卡牌 $i$ 立即被解锁了，因此处于卡牌 $j$ 到 $i$ 之间的卡牌选择什么都可以，显然，这里选择得分比选择解锁更优，因此，可以在转移时加上卡牌 $[k+1, i-1]$ 的权值之和，因此，有如下的转移方程：

dp[i][0] = \max_j^{j + a[j] \geq i}(dp[j][0] + \sum^{i-1}_{k=j+1}a_k)

dp[i][1] = dp[i][0] + a_i

其中的 $j$ 满足上述条件．最终状态即为 $dp[n][1]$ ．

不难发现，dp[x][1]（ $x\in\mathbb{N}^+$ ）没有在转移中提供过数据，因此可以舍去第二维，且默认第二维是 0．这样状态就变为了：考虑前 $i$ 张卡牌，且钦定第 $i$ 张需要用于解锁，所能够获取的最多金币．这样最终状态需要补上最后一张卡牌用于解锁相对用来获取金币所带来的损失（即 $a_n$ ），故最终状态为 $dp[n] + a_n$ ．

求区间和可以使用前缀和优化，总算法时间复杂度为 $O(n^2)$ ．

40pts 标程

1
#include <bits/stdc++.h>
2
#define sum(l, r) (s[(r)] - s[(l) - 1])
3
using namespace std;
4
const int N = 1e5 + 100;
5
int n, a[N], f[N], s[N];
6

7
void solve() {
8
    cin >> n;
9
    for (int i = 1; i <= n; i++) {
10
        cin >> a[i];
11
        s[i] = s[i - 1] + a[i];
12
        f[i] = -1e8;
13
    }
14
    f[1] = 0;
15
    for (int i = 1; i <= n; i++) {
16
        for (int j = 1; j < i; j++) {
17
            if (j + a[j] >= i) {
18
                f[i] = max(f[i], f[j] + sum(j + 1, i - 1));
19
            }
20
        }
21
    }
22
    int ans = a[1] + f[1];
23
    for (int i = 2; i <= n; i++) {
24
        ans = max(ans, a[i] + f[i]);
25
    }
26
    cout << ans << endl;
27
}
28

29
signed main() {
30
    int T;
31
    cin >> T;
32
    while (T--)
33
        solve();
34
    return 0;
35
}

考虑如何优化掉枚举 $j$ 的那一层循环．

上面的转移方程可以变形为下面的形式：

dp[i] = \max_j^{j + a[j] \geq i}((dp[j] - s[j]) + s[i-1])

若设 $v[j] = dp[j] - s[j],u[j]=j+a[j]$ ，则可以表示为：

dp[i]=s[i-1]+\max_j^{u[j] \geq i} v[j]

可以使用线段树动态维护最大值．每计算完一个点 $k$ 之后，将 $k$ 对应的 $v[k]$ 当作值， $u[j]$ 当作键加入线段树．在每一次计算时，查询在 $[1,i]$ 之间的元素的最大值，就可以使用 $O(\log n)$ 的时间复杂度计算 $\max_j^{u[j] \geq i} v[j]$ ．

标程

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
const int N = 1e5 + 100;
5
const int INF = 1e18;
6
int n, a[N], f[N], s[N];
7

8
struct SegmentTree {
9
    struct Node {
10
        int l, r, max;
11
        friend Node operator+(const Node a, const Node b) {
12
            if (a.max == -INF)
13
                return b;
14
            if (b.max == -INF)
15
                return a;
16
            Node nNode;
17
            nNode.max = std::max(a.max, b.max);
18
            nNode.l = a.l;
19
            nNode.r = b.r;
20
            return nNode;
21
        }
22
        static Node null() { return {0, 0, (int)-1e18}; }
23
    } f[N * 8];
24
    void build(int t, int l, int r) {
25
        if (l > r) {
26
            return;
27
        }
28
        f[t].l = l;
29
        f[t].r = r;
30
        if (l == r) {
31
            f[t].max = -INF;
32
            return;
33
        }
34

35
        int mid = (l + r) / 2;
36
        build(t * 2, l, mid);
37
        build(t * 2 + 1, mid + 1, r);
38
        pushup(t);
39
    }
40
    void pushup(int t) {
41
        int l = f[t].l, r = f[t].r;
42
        f[t] = f[t * 2] + f[t * 2 + 1];
43
        f[t].l = l;
44
        f[t].r = r;
45
    }
46
    Node query(int t, int x, int y) {
47
        if (x > y) {
48
            return Node::null();
49
        }
50
        if (x <= f[t].l && f[t].r <= y) {
51
            return f[t];
52
        }
53
        if (x > f[t].r || y < f[t].l) {
54
            return Node::null();
55
        }
56
        return query(t * 2, x, y) + query(t * 2 + 1, x, y);
57
    }
58
    void Modify(int t, int pos, int v) {
59
        if (f[t].l == pos && f[t].r == pos) {
60
            f[t].max = max(f[t].max, v);
61
            return;
62
        }
63
        if (f[t].l > pos || f[t].r < pos) {
64
            return;
65
        }
66
        Modify(t * 2, pos, v);
67
        Modify(t * 2 + 1, pos, v);
68
        pushup(t);
69
    }
70
} sgTree;
71

72
void solve() {
73
    cin >> n;
74
    for (int i = 1; i <= n; i++) {
75
        cin >> a[i];
76
        s[i] = s[i - 1] + a[i];
77
        f[i] = -INF;
78
    }
79
    sgTree.build(1, 1, n * 2);
80

81
    f[1] = 0;
82
    sgTree.Modify(1, 1 + a[1], f[1] - s[1]);
83
    int maxidx = 1 + a[1];
84

85
    for (int i = 2; i <= n; i++) {
86
        int qry = sgTree.query(1, i, maxidx).max;
87
        if (qry == -INF) {
88
            continue;
89
        }
90
        f[i] = qry + s[i - 1];
91
        sgTree.Modify(1, i + a[i], f[i] - s[i]);
92
        maxidx = max(maxidx, i + a[i]);
93
    }
94
    int ans = a[1] + f[1];
95
    for (int i = 2; i <= n; i++) {
96
        ans = max(ans, a[i] + f[i]);
97
    }
98
    cout << ans << endl;
99
}
100

101
signed main() {
102
    int T;
103
    cin >> T;
104
    while (T--)
105
        solve();
106
    return 0;
107
}

音乐

音乐

P10381 杂赛选比#

题目背景#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

【样例 1 解释】#

【样例 2 解释】#

【数据范围】#

文章分享

音乐

安吉D8-E

P10381 杂赛选比#

题目背景#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

【样例 1 解释】#

【样例 2 解释】#

【数据范围】#

文章分享