第六题 - A23471.圣诞礼物 题目链接跳转：A23471.圣诞礼物 一道很明显的完全背包问题，但需要加以优化。如果不优化的话，按照本题的数据量，在极端情况下程序会运行 105×105=101010^5 \times 10^5 = 10^{10}105×105=1010 次，大概需要 222 分钟时间（其实也不是很久）。因此我们需要在原本的完全背包的基础上加以优化： 通过观察可以发现，虽然物品的数量有 10510^5105 种，但是每种物品的花销却极其的少。就算有一个幸运数字为 888888888888888888888888888，那么也只需要 636363 个圣诞糖果就可以。假设有多个幸运数字都需要 101010 个糖果，那按照贪心的思路：如果我们要选支出则 636363 个圣诞糖果的话，我们可以获得的最大收益就是所有需要 101010 个糖果的幸运数字所对应的可以获得的金币数量的最大值。我们可以通过一个数组来记录对于每一种支付的糖果组合，可以获得的最大金币数量。 这样子我们就将原本的物品数量成功压缩成了 636363 种物品，即可通过本题的所有测试点。本题的 AC 代码如下： 本题的 Python 代码如下： 本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间的多项式时间复杂度约为 O(63M)O(63M)O(63M)，经过化简后的复杂度约为 O(M)O(M)O(M)。其中，数字 636363 代表最多存在 636363 中不同的“物品”。

首先，我们无脑用完全背包做 会发现这时间复杂度至少也得有O(nm)O(nm)O(nm)了，对于100000的数据肯定会超时 所以我们得用特殊的方法做 抽屉原理知道吧，跟这个没多大关系至少给了我们一些思路 ai≤109a_i\le10^9ai ≤109，即每个不超过十位数，那最多要的糖果就绝对不超过70 那这样重复的一大堆，我们只要找给的金币最大的就行了 这样就用凑零钱的方法就行了 C++解法 Python解法 时间复杂度：O(70n)O(70n)O(70n) 不得不说Python真的慢，C++24ms,Python1.6sC++24ms,Python1.6sC++24ms,Python1.6s

这题就是完全背包，但是有很多的数需要的火柴棍数量相同，用map择优加入其中即可。 代码： 这题虽然很简单但是赛时想了好久才想出来，导致提交次数非常多

题目解析 如果我们直接忽略数据范围，不难发现可以使用完全背包的DP模型来解决这道问题，定义 dp[i][j]dp[i][j]dp[i][j] 为前 iii 个礼物，使用 jjj 个糖果能够获得的最多金币。 但是注意到本题的数据范围 N,M (1≤N,M≤105)N, M\ (1 \le N, M \le 10^5)N,M (1≤N,M≤105) 如果使用上述递推式，时间复杂度为 O(N×M)\mathrm{O}(N \times M)O(N×M)。会超出本题的时间限制。 那么进一步分析题目我们会发现对于每个礼物 AiA_iAi ，制作出礼物需要的糖果为 f(Ai)f(A_i)f(Ai )，其中 1≤Ai≤1091 \le A_i \le 10^91≤Ai ≤109，我们不难发现，2≤f(Ai)≤632 \le f(A_i) \le 632≤f(Ai )≤63；而对于每个 f(Ai)f(A_i)f(Ai ) 由于可以重复制作同一种礼物，所以只需要取 max⁡Bi\max{B_i}maxBi 即可。 所以我们可以转换 dp[i][j]dp[i][j]dp[i][j] 定义为制作需要糖果数量不超过 iii 的礼物，使用 jjj 个糖果能够获得的最多金币。 那么此时的时间复杂度转化为 O(K×M)\mathrm{O}(K \times M)O(K×M) 其中 K=63K = 63K=63。 AC代码 C++ AC代码： Python AC代码： 复杂度分析 将所有的物品进行转化时间复杂度为 O(NW)\mathrm{O}(NW)O(NW)， 其中 W=10W = 10W=10； 动态规划的时间复杂度为 O(KM)\mathrm{O}(KM)O(KM)，其中 K=63K = 63K=63。 总的时间复杂度为 O(NW+MK)\mathrm{O}(NW + MK)O(NW+MK)。