Codeforces Round 889 (Div. 1) B. Earn or Unlock（dp，bitset）

题目链接：https://codeforces.com/problemset/problem/1854/B

题目大致题意：

有n张卡牌从上到下堆叠，每张卡片有锁或不锁俩种状态，一开始第一张是不锁的；

对最上面的卡牌，如果他是不锁的状态，那么可以进行俩种操作：

1：从上到下，将v张被锁的卡牌解锁；

2：获取v点能量

现在求能获得的最大的能量是多少？

解题思路：

一开始，我们可以观察到，解锁的卡牌一定是从上到下是连续，所以对于最终结果，一定是前a张卡牌被解锁的状态，后面的卡牌都是锁的状态；

那么我们可以知道，假设前k张卡牌被解锁，那么最终的结果是Σ ai - k + 1；

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

所以我们需要考虑是否存在k张卡牌解锁的情况；

那么这就是比较典 的问题了，用bitset来加速即可；

时间复杂度：O（n^2/w）；

代码：

#include<bits/stdc++.h>

const int N = 2e5 + 5;
std::bitset<N> dp;
long long sum;

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n; std::cin >> n;
    dp[1] = 1; sum = 0;

    long long ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        int x = 0;
        std::cin >> x;
        dp |= (dp << x);
        sum += x;
        if (dp[i])ans = std::max(ans, sum - i + 1), dp[i] = 0;
    }

    for (int i = n + 1; i <= 2 * n; ++i)
        if (dp[i])ans = std::max(ans, sum - i + 1);

    std::cout << ans << "\n";

    return 0;
}

当然，还是需要靠一点点小小的细节的，读者可以通过代码思考一下：）