本文主要是介绍洛谷P1450 硬币购物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：
P1450 [HAOI2008] 硬币购物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P1450
题干：
题目描述
共有 4 种硬币。面值分别为 c1,c2,c3,c4。
某人去商店买东西，去了 n 次，对于每次购买，他带了 di 枚 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。
输入格式
输入的第一行是五个整数，分别代表c1,c2,c3,c4,n。
接下来 n 行，每行有五个整数，描述一次购买，分别代表 d1,d2,d3,d4,s。
输出格式
对于每次购买，输出一行一个整数代表答案。
输入输出样例
输入 #1复制
1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900输出 #1复制
4 27说明/提示
数据规模与约定
- 对于 100% 的数据，保证 1≤ci,di,s≤10^5，1≤n≤1000。
这道题与前面那一道小球盒子的是一模一样。
我们大的方向还是从补集的角度。
它给了我们四种硬币，每个硬币给了限制，那么我所有的合法的答案，必然是花费的硬币少于限制的答案。由于它多了一个需要花s钱的条件，所以这题要用到递推dp。
首先算全集，也就是没有任何限制，我们只需要花钱买s钱的物品即可。
那么总共的方案数 就是
假如第一种硬币超过限制，我们不管超过多少，只需要让第一种硬币 先花费d1+1 个，
然后 剩下的钱：s - c1*（d1+1） .
如果剩下的钱大于0，就让四种硬币随便组合凑出 s - c1*（d1+1）元，返回其答案即可
如果剩下的钱小于0，就直接是 0种可能
指定一种硬币超限其他不管，一共有4种可能，
然后下一种就是指定两种硬币超限，其他不管。
指定3种硬币超限……
指定4种硬币超限……
我们只需要求出这四种情况的并集即可。
由容斥定理可以知道 四种情况的并集为：奇数-偶数
也就是奇数种硬币超限-偶数种硬币超限
最后用 全集减去并集，就是得到的答案。
（全集减去并集，符号改变，也就是变成偶数-奇数）
那么在此之前我们必须要用完全背包处理预处理一下无限硬币的情况就好了。
上答案：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const int MAXN =1e5 ;
typedef long long ll;
long long dp[MAXN+5];long long get(long long x) {if (x < 0)return 0;return dp[x];
}
int main() {ll c[10];dp[0] = 1;for (ll i = 1; i <= 4; i++) {cin >> c[i];for (ll j = c[i]; j <= MAXN; j++) {dp[j] += dp[j - c[i]];}}ll q;cin >> q;while (q--) {ll d[10],s;for (ll i = 1; i <= 4; i++) {cin >> d[i];d[i] = (d[i] + 1) * c[i];}cin >> s;cout<< get(s) - get(s - d[1]) - get(s - d[2]) - get(s - d[3]) - get(s - d[4]) + get(s - d[1] - d[2]) + get(s - d[1] - d[3]) + get(s - d[1] - d[4]) + get(s-d[3] - d[2]) + get(s - d[4] - d[2]) + get(s - d[3] - d[4]) - get(s - d[1] - d[2] - d[3]) - get(s - d[1] - d[2] - d[4]) - get(s - d[4] - d[2] - d[3]) - get(s - d[1] - d[3] - d[4]) + get(s - d[1] - d[2] - d[3] - d[4]) ;cout <<endl;}
}这篇关于洛谷P1450 硬币购物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
