首页 > 代码库 > [BZOJ 1042] [HAOI2008] 硬币购物 【DP + 容斥】
[BZOJ 1042] [HAOI2008] 硬币购物 【DP + 容斥】
题目链接：BZOJ - 1042
题目分析
首先 Orz Hzwer ，代码题解都是看的他的 blog。
这道题首先使用DP预处理，先求出，在不考虑每种硬币个数的限制的情况下，每个钱数有多少种拼凑方案。
为了避免重复的方案被转移，所以我们以硬币种类为第一层循环，这样阶段性的增加硬币。
一定要注意这个第一层循环要是硬币种类，并且初始 f[0] = 1。
f[0] = 1;for (int i = 1; i <= 4; ++i) { for (int j = B[i]; j <= MaxS; ++j) { f[j] += f[j - B[i]]; }}之后对于每个询问 (A1, A2, A3, A4, S) ，根据容斥原理，我们要求的答案 Ans 就是 f[S] - (硬币1超限制的方案数) - (硬币2超限制的方案数) - (硬币3超限制的方案数) - (硬币4超限制的方案数) + (硬币1,2超限制的方案数) + (硬币1,3超限制的方案数) + (硬币1,4超限制的方案数) + .... - (硬币1,2,3超限制的方案数) - ... + (硬币1,2,3,4超限制的方案数) 。
怎样求硬币1超限制的方案数呢？我们只要先固定取 (A1+1) 个硬币1，剩余的钱数随便取就可以了，就是 f[S - (A1+1) * V[1]] 。
其余的情况都类似。
容斥的部分使用搜索实现。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>using namespace std;const int MaxN = 7, MaxS = 100000;int n, S;int A[MaxN], B[MaxN];typedef long long LL;LL Ans;LL f[MaxS + 5];void DFS(int x, int k, int Sum) { if (Sum < 0) return; if (x == 5) { if (k & 1) Ans -= f[Sum]; else Ans += f[Sum]; return; } DFS(x + 1, k + 1, Sum - (A[x] + 1) * B[x]); DFS(x + 1, k, Sum);}int main() { for (int i = 1; i <= 4; ++i) scanf("%d", &B[i]); scanf("%d", &n); f[0] = 1; for (int i = 1; i <= 4; ++i) { for (int j = B[i]; j <= MaxS; ++j) { f[j] += f[j - B[i]]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 4; ++j) scanf("%d", &A[j]); scanf("%d", &S); Ans = 0ll; DFS(1, 0, S); printf("%lld\n", Ans); } return 0;}
[BZOJ 1042] [HAOI2008] 硬币购物 【DP + 容斥】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。