【容斥+完全背包】P1450 [HAOI2008] 硬币购物

不念不忘少年蓝@ 2024-03-17 09:00 27阅读 0赞

[P1450 \[HAOI2008\] 硬币购物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1450 _HAOI2008_ _ - _ _ _ _luogu.com.cn]

题意：

![fc32bedf37bd4e09a396ad746c016511.png][]

![1ad46e7d25dd495697113aa7d11f820c.png][]

思路：

![b81adb72abf34a3496f89002c19637b8.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    long long c[5],d[5],ans,tot,s,f[100005],k;
    
    signed main()
    {
    	for(int i = 1; i <= 4; i++) scanf("%d",&c[i]); scanf("%d",&tot);
    	f[0] = 1;
    	for(int j = 1; j <= 4; j++)
    		for(int i = 1; i <= 100000; i++)
    			if(i >= c[j]) f[i] = f[i] + f[i - c[j]];
    	while(tot--)
    	{
    		for(int i = 1; i <= 4; i++) scanf("%d",&d[i]);
    		scanf("%d",&s);
    		ans = f[s];
    		for(int k = 15;k > 0; k--)
    		{
    			long long u = 0,o = k,now = 0,cnt = 0;
    			while(o > 0)
    			{
    				cnt++;
    				if(o & 1)
    				{
    					now = (d[cnt] + 1) * c[cnt] + now;
    					u ^= 1;
    				}
    				o >>= 1;
    			}
    			if(now > s) continue;
    			if(u) ans -= f[s - now];
    			else ans += f[s - now];
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[P1450 _HAOI2008_ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1450#submit
[fc32bedf37bd4e09a396ad746c016511.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/20cd5d9ac5294b96bd4b742832dffcbf.png
[1ad46e7d25dd495697113aa7d11f820c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/60d980fe54b845f6980224a5b5441411.png
[b81adb72abf34a3496f89002c19637b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/dab04c898acd4a299b1b70f507e96f6c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-完全背包硬币组合问题

1. 硬币组合问题给定硬币的面值数组，以及需要找零的目标值 target，输出能满足要求的最小硬币数量。例如： coins = \[1, 2, 5\], amo...

ゞ浴缸里的玫瑰/ 2024年04月18日 14:58/ 0 赞/ 76 阅读

相关【容斥+完全背包】P1450 [HAOI2008] 硬币购物

[P1450 \[HAOI2008\] 硬币购物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1450 _HAOI2008_ _ - _ _ _ _l

不念不忘少年蓝@/ 2024年03月17日 09:00/ 0 赞/ 28 阅读

相关 lintcode 669. 换硬币完全背包

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1. 样例

约定不等于承诺〃/ 2023年07月25日 11:26/ 0 赞/ 11 阅读

相关【HAOI2008】硬币购物

Description [【HAOI2008】硬币购物][HAOI2008] 给定4种硬币的价值。若干组询问，每次给出4种硬币的数量和要购买的花费，求恰好购买的方案数

妖狐艹你老母/ 2023年06月05日 08:54/ 0 赞/ 29 阅读

相关【bzoj】1042: [HAOI2008]硬币购物

1042: \[HAOI2008\]硬币购物 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2371 Solved: 1

比眉伴天荒/ 2022年09月30日 15:59/ 0 赞/ 149 阅读

相关 P02: 完全背包问题

题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容

短命女/ 2022年01月28日 00:45/ 0 赞/ 231 阅读

相关容斥原理

目录容斥原理基本的容斥原理反演二项式反演 Möbius反演容斥原理大力推荐《组合数

深碍√TFBOYSˉ_/ 2021年12月16日 03:04/ 0 赞/ 386 阅读

相关 P2512 [HAOI2008]糖果传递

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n

港控/mmm°/ 2021年09月30日 07:04/ 0 赞/ 350 阅读

相关题解 P2512 [HAOI2008]糖果传递

首先我们要用到一些[均分纸牌][Link 1]的思想(已经理解这种思想的大佬请跳过): 设\\(A\_i\\)表示第\\(i\\)个小朋友原有的糖果数量, 设\\(ave\

小鱼儿/ 2021年09月29日 11:56/ 0 赞/ 281 阅读

相关 Bzoj1042: [HAOI2008]硬币购物

Sol 容斥原理+背包处理出所有金币无限制条件凑成\(j\)元的方案数考虑计算 \(c\)只有\(4\)种，可以容斥一波就是无限制的总方案-\(1\)个硬币超出限制...

朱雀/ 2021年03月28日 15:40/ 0 赞/ 475 阅读