【题目来源】
洛谷：P1450 [HAOI2008] 硬币购物 - 洛谷
【题目描述】
共有 \(4\) 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。
某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了 \(d_i\) 枚 \(i\) 种硬币，想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。
【输入】
输入的第一行是五个整数，分别代表 \(c_1,c_2,c_3,c_4,n\)。
接下来 \(n\) 行，每行有五个整数，描述一次购买，分别代表 \(d_1,d_2,d_3,d_4,s\)。
【输出】
对于每次购买，输出一行一个整数代表答案。
【输入样例】
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
【输出样例】
4
27
【算法标签】
《洛谷 P1450 硬币购物》 #动态规划,dp# #数学# #递推# #容斥原理# #各省省选# #河南# #2008#
【代码详解】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long LL;
int c[4], d[4], n, s; // c: 硬币面值, d: 每种硬币的限制数量, n: 查询次数, s: 目标金额
LL f[100005]; // f[j]: 用无限硬币组成金额j的方案数（不考虑限制）// 完全背包预处理：计算不考虑硬币数量限制时，组成各种金额的方案数
void pack_pre()
{ // 完全背包预处理f[0] = 1; // 金额为0只有一种方案：不选任何硬币for (int i = 0; i < 4; i++) // 遍历4种硬币{for (int j = c[i]; j < 100005; j++) // 完全背包正向遍历{f[j] += f[j - c[i]]; // 状态转移：使用第i种硬币}}
}// 容斥原理计算：在硬币数量限制下，组成金额s的方案数
LL calc(LL s)
{ // 容斥原理计算LL res = 0;// 枚举所有非空子集（使用状态压缩，i从1到15）for (int i = 1; i < 1 << 4; i++){// 枚举状态LL t = 0, sign = -1; // t: 超过限制的硬币总金额, sign: 容斥系数（初始为-1）for (int j = 0; j < 4; j++) // 过滤状态{if (i & 1 << j) // 如果第j种硬币被选中（即违反限制）{t += c[j] * (d[j] + 1); // 这种硬币至少使用了d[j]+1个sign = -sign; // 改变容斥系数符号}}if (s >= t) // 如果目标金额s大于等于超过限制的总金额{res += f[s - t] * sign; // 应用容斥原理}}return f[s] - res; // 总方案数减去违反限制的方案数
}int main()
{// 读入4种硬币的面值for (int i = 0; i < 4; i++){scanf("%d", &c[i]);}pack_pre(); // 预处理完全背包scanf("%d", &n); // 读入查询次数while (n--){// 读入每种硬币的限制数量for (int i = 0; i < 4; i++){scanf("%d", &d[i]);}scanf("%d", &s); // 读入目标金额printf("%lld\n", calc(s)); // 计算并输出结果}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
#define int long long
int c[4], d[4], n, s; // c: 硬币面值, d: 每种硬币的限制数量, n: 查询次数, s: 目标金额
int f[N]; // f[j]: 完全背包，不考虑限制时组成金额j的方案数// 完全背包预处理：计算不考虑硬币数量限制时，组成各种金额的方案数
void pack_pre()
{f[0] = 1; // 金额为0只有一种方案：不选任何硬币for (int i = 0; i < 4; i++) // 遍历4种硬币{for (int j = c[i]; j < 100005; j++) // 完全背包正向遍历{f[j] += f[j - c[i]]; // 状态转移：使用第i种硬币}}
}// 容斥原理计算：在硬币数量限制下，组成金额s的方案数
int calc(int s)
{int res = 0; // 违反限制的方案数总和（带容斥系数）// 枚举所有非空子集（状态压缩，1到15）for (int i = 1; i < (1 << 4); i++) // 遍历所有硬币组合{int t = 0, cnt = 0; // t: 超过限制的最小总金额, cnt: 违反限制的硬币种类数// 检查哪些硬币违反了限制for (int j = 0; j < 4; j++) // 遍历4种硬币{if (i >> j & 1) // 如果第j位为1，表示第j种硬币违反限制{cnt++; // 违反限制的硬币种类数加1t += c[j] * (d[j] + 1); // 这种硬币至少使用d[j]+1个}}// 如果目标金额大于等于违反限制所需的最小金额if (s >= t){// 根据容斥原理：奇数个违反限制时加，偶数个违反限制时减if (cnt % 2) // 奇数个违反限制{res += f[s - t]; // 加上违反限制的方案数}else // 偶数个违反限制{res -= f[s - t]; // 减去违反限制的方案数}}}return f[s] - res; // 总方案数减去违反限制的方案数
}signed main()
{// 读入4种硬币的面值for (int i = 0; i < 4; i++){cin >> c[i];}pack_pre(); // 预处理完全背包cin >> n; // 读入查询次数while (n--) // 处理每个查询{// 读入每种硬币的限制数量for (int i = 0; i < 4; i++){cin >> d[i];}cin >> s; // 读入目标金额cout << calc(s) << endl; // 计算并输出结果}return 0;
}
【运行结果】
1 2 5 10 2
3 2 3 1 10
4
1000 2 2 2 900
27