ZROI P2577 题解

题面

点击此处展开题面

电车难题

1997年，小 X 学会了开电车。于是他决定和小 R 做一个游戏。

小 X 会驾驶电车依次经过 $n$ 个分叉口。在第 $i$ 个分叉口，如果不做行动，电车会驶向上方的轨道，并获得 $a_i$ 个积分。另外，小X可以请小R扳动第 $i$ 个路口的道岔，从而让电车驶向下方的轨道，并获得 $b_i$ 个积分。

注意：电车在第 $i + 1$ 个分叉口的行动不会受前 $i$ 个分叉口的影响。

不过小R多次扳动道岔会不耐烦，因此如果小 R 总共扳动了 $m$ 次道岔，小 X 会失去 $1 + 2 + 3 + \ldots +m$ 个积分。

小 X 想知道，他最终最多能获得多少积分。

输入格式

第一行一个整数 $n$，表示分叉口的数量。

第二行 $n$ 个整数，表示 $a_1, a_2 , \ldots, a_n$。

第三行 $n$ 个整数，表示 $b_1, b_2 , \ldots, b_n$。

输出格式

一行一个整数，表示获得的最多积分。

样例

输入：

8
1 9 5 3 0 6 1 5
3 9 7 6 0 13 3 7

输出：

37

数据范围

对于 30% 的数据，$n \leq 20$。

对于 100% 的数据，$n \leq 4 \times 10^4, 0 \leq a_i, b_i \leq 5 \times 10^4$。

解题

看到题，第一时间应该想到 dp。

当 dp 做的思路

问题定义

大问题：前 $n$ 个路口的最大积分。

小问题：前 $i$ 个路口扳动 $j$ 次的最大积分。

状态定义

$f_{i,j}$ := 前 $i$ 个路口扳动 $j$ 次的最大积分

状态转移

对于第 $i$ 个路口 $(i >= 1, j <= i)$：

• 如果扳动：$f_{i,j} = f_{i - 1,j - 1} + b_i - j$
• 如果不动：$f_{i,j} = f_{i - 1,j} + a_i$

两个中取最大。

答案

$$max(f_{n, 0}, f_{n, 1}, \ldots, f_{n, n})$$

边界

$$f_{i, 0} = f_{i - 1,0} + b_i \\ f_{0, j} = 0 \\ f_{0, 0} = 0$$

压缩

用两个数组交替使用，或滚动数组。

虽然这道题 dp 不是正解，但卡常貌似能过（靠运气

详情

注意

卡常有风险，复制需谨慎！

作者懒没卡常，需要者请自行发挥。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 4e4 + 5;
LL a[N], b[N];
LL f1[N], f2[N];
LL (*current)[N] = &f1, (*last)[N] = &f2;

int main() {
  register int n, m = 1;
  scanf("%llu", &n);
  for (register int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (register int i = 1; i <= n; ++i) scanf("%d", &b[i]);
  register LL ans = 0;
  for (register int i = 1; i <= n; ++i) {
    swap(current, last);  // 避免使用 memcpy
    (*current)[0] = (*last)[0] + a[i];
    for (register int j = 1; j <= i; ++j) {
      if (i == j) {
        (*current)[j] = (*last)[j - 1] + b[i] - j;
      } else {
        (*current)[j] = max((*last)[j - 1] + b[i] - j, (*last)[j] + a[i]);
      }
    }
  }
  for (register int i = 0; i <= n; ++i) ans = max(ans, (*current)[i]);
  printf("%llu", ans);
  return 0;
}

::::

那正解如何呢？

由于一个决策不会对后续的路线产生影响，那么我们可以任意更换路口的顺序，答案不变。

可以采用贪心思想，为了最大化收益，优先扳动 $b_i$ 比 $a_i$ 大得多的。

关于题中不耐烦的扣分，只需要在判断大小时额外减去即可。

所以，我们可以按 $b_i - a_i$ 对 $a$ 和 $b$ 进行降序排序，再从头（$b_i - a_i$ 最大）开始扳动。

除去不耐烦的扣分，这样就能保证从大到小取到收益，也就是答案是一段前缀。

关于不耐烦的扣分，由于顺序不影响答案，并且答案是一段前缀，第 $i$ 个就扣 $i$ 分。

代码

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 4e4 + 5;
LL a[N], b[N];
LL d[N];  // 每个路口扳动后积分的变化量（不耐烦的扣分除外）

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &b[i]);
    d[i] = b[i] - a[i];  // 顺便计算 `d`
  }
  sort(d + 1, d + n + 1, [](int a, int b) { return a > b; });
  LL ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > i) ans += d[i] - i;  // 这里减掉不耐烦的扣分
    ans += a[i];                    // 不扳动的都要加
  }
  printf("%lld", ans);
  return 0;
}