Bzoj1042: [HAOI2008]硬币购物

朱雀 2021-03-28 15:40 378阅读 0赞

# Sol #

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

# include <bits/stdc++.h> # define RG register # define IL inline # define Fill(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; const int _(1005); IL int Input(){ RG int x = 0, z = 1; RG char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * z; } typedef int Arr[_]; int c[4], tot, mx, pw[4] = {1, 2, 4, 8}, s[_], d[4][_]; ll f[_ * 100] = {1}, ans; int main(RG int argc, RG char *argv[]){ for(RG int i = 0; i < 4; ++i) c[i] = Input(); tot = Input(); for(RG int i = 1; i <= tot; ++i){ for(RG int j = 0; j < 4; ++j) d[j][i] = (Input() + 1) * c[j]; s[i] = Input(), mx = max(mx, s[i]); } for(RG int i = 0; i < 4; ++i) for(RG int j = c[i]; j <= mx; ++j) f[j] += f[j - c[i]]; for(RG int i = 1; i <= tot; ++i){ ans = 0; for(RG int j = 0; j < 16; ++j){ RG int op = 1, sum = 0; for(RG int k = 0; k < 4; ++k) if(j & pw[k]) op = -op, sum += d[k][i]; ans += (sum > s[i]) ? 0 : (1LL * op * f[s[i] - sum]); } printf("%lld\n", ans); } return 0; }

发表评论取消回复

表情：

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

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

相关阅读

相关「BZOJ 4565」「HAOI 2016」字符合并「区间状压DP」

题意给一个长度为\\(n(\\leq 300)\\)的\\(01\\)串，每次可以把\\(k(\\leq 8)\\)个相邻字符合并，得到新字符和一定分数，最大化最后的得分

ゝ一世哀愁。/ 2023年08月17日 17:31/ 0 赞/ 66 阅读

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

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

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

相关 BZOJ 1041: [HAOI2008]圆上的整点

1041: \[HAOI2008\]圆上的整点 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2951 Solved

傷城~/ 2022年07月29日 08:41/ 0 赞/ 89 阅读

相关 bzoj4035【HAOI2015】数组游戏

题目描述有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的

淡淡的烟草味﹌/ 2021年12月23日 01:45/ 0 赞/ 132 阅读

相关【洛谷 P2512】 [HAOI2008]糖果传递（贪心）

[题目链接][Link 1] 环形均分纸牌。设平均数为\\(ave\\),\\(g\[i\]=a\[i\]-ave\\),\\(s\[i\]=\\sum\_\{j=1

深藏阁楼爱情的钟/ 2021年12月21日 06:37/ 0 赞/ 182 阅读

相关 BZOJ 2427: [HAOI2010]软件安装 tarjan + 树形背包

Code: include<bits/stdc++.h> using namespace std; define setIO(s) freope

迈不过友情╰/ 2021年11月17日 16:18/ 0 赞/ 202 阅读

相关 P2512 [HAOI2008]糖果传递

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

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

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

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

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

相关 [LUOGU] P4290 [BZOJ] 1055 [HAOI2008]玩具取名

题目描述某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WIN

小咪咪/ 2021年09月29日 02:50/ 0 赞/ 193 阅读

相关 Bzoj1042: [HAOI2008]硬币购物

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

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