CF1854B Earn or Unlock 题解

· · 题解

本题有一个重要的性质：设最终包括 1 号卡片总共解锁了 k 张卡片，则所获得的分数就是 \sum_{i = 1}^{k} a_i - k + 1。

感性理解：如果将一张权值为 x 的卡片用来解锁接下来的 x 张卡片，那么相比于用它换取 x 分，就相当于损失了 x 分。因此，我们解锁了 k - 1 张卡片（不包括 1 号卡片），就要损失 k - 1 分。

所以，我们只用判断是否存在一种方案使得恰好解锁 k 张卡片即可。考虑用 bitset 加速 dp。

设 bool 类型的 dp[i] 表示是否存在一种方案使得恰好解锁 i 张卡片。初始时 dp[1] = 1 （因为 1 号卡片初始已被解锁）。对于每一张权值为 a_i 的卡片，如果存在一种方案使得恰好解锁 j 张卡片，则我们可以消耗这张卡片使得恰好解锁 j + a_i 张卡片。转移方程式如下：

dp[j] = dp[j] \ \textrm{or} \ dp[j - a_i]

直接这样写会 TLE，考虑将 dp 数组定义为一个 bitset，用 bitset 加速转移：

dp = (dp | (dp << a[i]));

注意，做完这句语句后，要将 dp[i] 设为 0（因为此时已经遍历过前 i 张卡片了，接下来枚举的卡片已经超出了前 i 张卡片的范围，此时我们只解锁了前 i 张卡片，不能使用编号大于 i 的卡片）。为方便查询，可以先用别的数组记录 dp[i] 的值，然后将 dp[i] 设为 0。

最后枚举解锁的卡片的数量 k，如果存在一种方案使得恰好解锁 k 张卡片，那么将 \sum_{i = 1}^{k} a_i - k + 1 与 ans 取最大值。

注意， dp 数组要开到 2n 的大小，枚举解锁的卡片的数量 k 时也要枚举到 2n。详见代码。（我就因为这个而 WA#7）

原因是，有可能可以解锁的卡片数量超过了 n。具体可以看下面这组样例。

2
2 114514

正确的输出应为 114514，是因为 dp[3] = 1，如果不枚举到 2n，就无法处理这种情况。

下面给出代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 200000;
const ll N = maxn + 10;
ll n, m, ans, a[N], s[N];
bool f[N];
bitset<N> dp;
int main() {
    scanf("%lld", &n);
    s[0] = 0;
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    dp[1] = 1;
    for (ll i = 1; i <= n; ++i) {
        dp = (dp | (dp << a[i]));
        f[i] = dp[i];
        dp[i] = 0;
    }
    for (ll i = n + 1; i <= 2 * n; ++i) {
        f[i] = dp[i];
        s[i] = s[i - 1];
    }
    ans = 0;
    for (ll i = 1; i <= 2 * n; ++i) {
        if (f[i]) {
            ans = max(ans, s[i] - i + 1);
        }
    }
    printf("%lld", ans);
    return 0;
}

蒟蒻讲的有些地方可能有点啰嗦或者不清楚，还请巨佬们谅解！