2025-12-14题目：Codeforces Round 1068 (Div. 2) B

约 443 字大约 1 分钟

动态规划贪心

2025-12-14

题源

https://codeforces.com/contest/2173/problem/B

题意

Nike正在进行一个 $n$ 轮的游戏，初始得分 $k$ 为0。每一轮得到一张红牌值 $a_i$ 和一张蓝牌值 $b_i$ 。如果选择红牌，那么她的分数变为 $k - a_i$ ，选择蓝牌变为 $b_i - k$ 。问最多可得多少分。

轮数不超过 $10^5$ ， $a_i, b_i$ 均为整数且绝对值不超过 $10^9$ 。限时为1.5秒。

提示

每次都选择使结果最大的一张牌，这种解法是否可行？为什么？
后面一个选择哪一张好，和前面的选择了哪些密切相关。

题解

每次都选择使结果最大的一张牌不可行。例如 $(a_i, b_i) = [(2, 1), (0, 0)]$ ，若第一次选择使结果最大的红牌，得到1，但接下来第二次结果是-1或1。而第一次选择使结果较小的，得到-2，接下来结果是2或-2。问题在于，要使得选择蓝牌的 $b_i - k$ 最大，就要 $k$ 最小，而我们的策略使得 $k$ 总是较大的。

这里我们可以记录下两个值，截止目前能选到的最大值和最小值，供后面选择。不难发现，存在 $max_i = \max(max_{i-1}-a_i, b_i-min_{i-1})$ 和 $min_i = \min(min_{i-1}-a_i, b_i-max_{i-1})$ 两个状态变化过程，且最终 $max_n$ 就是答案。可以在 $O(n)$ 时间复杂度内得到答案。

部分代码

温馨提醒：不开long long见祖宗。

ll mx = 0;
ll mi = 0;
for (int i = 1; i <= n; i ++) {
	ll mx2 = max(mx - a[i], b[i] - mi);
	ll mi2 = min(mi - a[i], b[i] - mx);
	mx = mx2;
	mi = mi2;
}
cout << mx << "\n";