题解：SP30738 ADACOINS - Ada and Coins

· · 题解

题解前几个怎么全是火车头。

这道题目的算法是背包 DP，不难发现，我们亲爱的“题目翻译”把题目给精简化了，所以题目就这几句话：

有 n 个物品，第 i 个物品价值 A _ {i} 元，现在问你 q 次，从 l 到 r 中，最多能组合出多少种价值（每个物品只能用一次）？

这一看，这岂不是 01 背包 DP？

状态转移方程：dp_{i,j}=dp_{i,j} \vee dp_{i-1,j-w_{i}}。

但状态与普通背包不同，这里 dp _ {i} 表示是否可以组合出 i。

仔细思考后发现，这题不能开 DP 数组！应该使用 std::bitset 优化！

不难发现，DP 数组的每个元素始终保持着存储 0 或 1，就和二进制很像！而 std::bitset 则就是把他当成一个二进制数，自然空间会小很多。

我们每次就是要从上一个状态中推过来，所以 bitset 一个就够了，这算是滚动优化。

于是乎推出公式：dp = dp \vee (dp \times 2 ^ {a_{i}})。

且可以用位运算在 \Theta(1) 的时间复杂度内计算出。

最后，我们给 DP 数组加个前缀和即可！

在原 OJ 上已 AC！（在洛谷没绑号，可不是没 AC 发题解啊！）

#include <bits/stdc++.h>
using namespace std;
int a[100007];
bitset<100007> dp;
int pr[100007]; // 前缀和
int n, q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n >> q;
    dp[0] = 1; // 很显然，0是一定拼的出来的。
    pr[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp |= dp << a[i]; // 公式，不再赘述。
    }
    for (int i = 1; i <= 100000; i++)
        pr[i] = pr[i - 1] + dp[i]; // 前缀和
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << pr[r] - pr[l - 1] << '\n'; // 前缀和直接O(1)处理。
    }
    return 0;
}

给个赞再走呗……