首页 > [HAOI2008]硬币购物
开通博客写题解
头像 __故人__
发表于 2020-09-23 16:16:38
分析 背包 题。因为朴素的 的时间复杂度为 应该过不去。那么换种思路，先考虑没有个数限制，令 为考虑前 种物品，体积为 时，总的方案数。发现我们对个数的限制可以考虑子集容斥。考虑到，恰好选 个的方案数是等于至少选 个的方案数减去至少选 的方案数。那么现在是让我们求恰好选 到 个 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 shyyhs
发表于 2020-09-24 01:33:18
讲真的看到题,我都没想容斥原理...是我太菜了吗.首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...其实假设我们只能 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Dear㉿You
发表于 2020-09-28 10:15:28
分析 我的心理反应：要是没有个数限制多好啊QwQ 于是：我们先处理出一个完全背包，求出每一种容量拼凑的方案数。这时，如果要求s，那么肯定会有用超过个数的 那么这时不可取的，就得减去这些超过个数的不合法方案。根据容斥原理，我们在减去1,2,3,4超限制的同时，多减 了一部分，还要在加回来，然后 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 林思艺
发表于 2020-09-23 17:17:22
一眼看去，就是个多重背包嘛~~ 但是看一下数据范围，emm，好的，换思路。 首先考虑，如果没有次数限制的话，那么直接完全背包预处理，然后询问就好了。 然后考虑容斥，从中减去不合法的方案。首先肯定会有一种硬币超额使用，对于第种硬币等于说强制选了个，剩下的依然随便选，那么对于第种硬币不合法的方案数等于， 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 熠丶
发表于 2020-09-23 15:30:57
刚看到题，直接想到多重背包的做法，于是写了一个裸多重背包（没有进行什么优化），很显然就t了https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45065555&returnHomeType=1&uid=42 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-23 16:32:53
吐槽 看完题之后的心理反应:这这?不是一个数学小蓝皮上母函数的模板题吗想了一会儿,发现还是WTCL 分析 一道简单的容斥DP题我们发现我们先考虑一下弱化版本如果每个硬币都不受限那么我们就可以直接暴力背包求得所有方案书 所以我们现在来考虑一下本题发现,我们可以容斥解决先把答案设为DP[Cost]然后减 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-23 19:50:53
[HAOI2018]硬币购物 都这年头了，还有谁购物用硬币的吗？ 题目大意 首先，你有四种面值的硬币 然后你会出门采购次 每次出门，你都会带上一些硬币，每种硬币的个数给定 然后你买了的东西 问你有多少种付款的方案 分析 直接写裸的背包的时间复杂度直接炸天 那么正难则反是一个十分优秀的想法 就是说，可 展开全文
去ta的博客 赞 (2) 回复(4) 收起
头像 sunrise__sunrise
发表于 2020-09-28 22:34:37
题目意思 你来到一个商店，你带了c1,c2,c3,c4四种面值的硬币，以及购买次数tot。接下来tot行，每行有d1,d2,d3,d4分别对应四种硬币的使用个数上限，以及你想要购买的物品价值数s。询问你有几种合理的方法使用合理的硬币数量购买到价值s的物品？ Solution 正面？处理不来，情况太多 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 灯又烬
发表于 2020-09-24 11:27:06
题意 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。 题解 一眼看去一个多重背包dp...再一眼看去数据范围..1e5这样暴力背包就t了.可以转换想法，假设硬币的枚数没有限制，这样在每一组 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”