官方题解｜圣诞礼物

题目解析

如果我们直接忽略数据范围，不难发现可以使用完全背包的DP模型来解决这道问题，定义 $dp[i][j]$ 为前 $i$ 个礼物，使用 $j$ 个糖果能够获得的最多金币。

但是注意到本题的数据范围 $N, M\ (1 \le N, M \le 10^5)$ 如果使用上述递推式，时间复杂度为 $\mathrm{O}(N \times M)$。会超出本题的时间限制。

那么进一步分析题目我们会发现对于每个礼物 $A_i$，制作出礼物需要的糖果为 $f(A_i)$，其中 $1 \le A_i \le 10^9$，我们不难发现，$2 \le f(A_i) \le 63$；而对于每个 $f(A_i)$ 由于可以重复制作同一种礼物，所以只需要取 $\max{B_i}$ 即可。

所以我们可以转换 $dp[i][j]$ 定义为制作需要糖果数量不超过 $i$ 的礼物，使用 $j$ 个糖果能够获得的最多金币。

那么此时的时间复杂度转化为 $\mathrm{O}(K \times M)$ 其中 $K = 63$。

AC代码

C++ AC代码：

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int K = 7 * 9;

constexpr int cnt[] {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int f(int x) {
    return x < 10 ? cnt[x] : cnt[x % 10] + f(x / 10);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x;
        for (auto &x : b) cin >> x;
        int val[K + 1]{};
        for (int i = 0; i < n; ++i) {
            int x = f(a[i]);
            val[x] = max(val[x], b[i]);
        }
        vector<i64> dp(m + 1);
        for (int i = 1; i <= K; ++i)
            for (int j = i; j <= m; ++j)
                dp[j] = max(dp[j], dp[j - i] + val[i]);
        cout << dp[m] << '\n';
    }
    return 0;
}

Python AC代码：

cnt = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
K = 7 * 9

def f(x: int)->int:
    return cnt[x] if x < 10 else f(x // 10) + cnt[x % 10]

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    val = [0] * (K + 1)
    for i, v in enumerate(map(int, input().split())):
        x = f(a[i])
        if val[x] < v:
            val[x] = v
    dp = [0] * (m + 1)
    for i in range(1, K + 1):
        if val[i] == 0:
            continue
        for j in range(i, m + 1):
            if dp[j - i] + val[i] > dp[j]:
                dp[j] = dp[j - i] + val[i]
    print(dp[m])

复杂度分析

将所有的物品进行转化时间复杂度为 $\mathrm{O}(NW)$， 其中 $W = 10$；
动态规划的时间复杂度为 $\mathrm{O}(KM)$，其中 $K = 63$。
总的时间复杂度为 $\mathrm{O}(NW + MK)$。