洛谷P1450.硬币购物

题目大意：4种面值c[i]的硬币，每种硬币持有d[i]个，问有多少种方法支付出正好N块钱。

可以先预处理出持有硬币无限的情况dp[n]，即一个完全背包问题。

之后根据容斥原理，相当于求 $\sum_{i=1}^{n}c_{i}x_{i}=S$ 但是拥有限制 $x_i\leq d_{i}$ ，可以参考有限制的不定方程非负整数解的容斥方法，我们设全集 $U$ 为所有在无限情况下凑出S的方案数，属性为 $x_i\leq d_{i}$ ，那么就可以对所有补集的并用容斥原理展开进行计算，对于每个 $\left | \bigcap_{a_{i}<a_{i+1}}^{|a|=k}\overline{S_{a_{i}}} \right |$ 是由具有k个不同反向性质 $x\geq d_{i}+1$ 组成的集合，对应在容斥式子中的答案就是在无限情况下凑出 $\sum_{i=1}^{n}c_{i}x_{i}=m-\sum_{i=1}^{k}c_{i}(d_{a_{i}}+1)$ 的方案数即 $dp[m-\sum _{i=1}^{k}c_{i}(d_{a_{i}}+1)]*(-1)^{k-1}$ 。

最后用全集减去就可以了。

#include<bits/stdc++.h>

#include<unordered_map>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

//#define int LL

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3f

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#pragma warning(disable :4996)

const int maxn = 100010;

const int mod = 1e9 + 7;

const double eps = 1e-8;

LL c[5], N;

LL d[5], S;

LL dp[maxn];

void solve()

{

	memset(dp, 0, sizeof(dp));

	dp[0] = 1;//价格为0时无限硬币组成之方法数

	for (LL i = 1; i <= 4; i++)

	{

		for (LL j = 0; j <= S; j++)

		{

			if (j - c[i] >= 0)

				dp[j] += dp[j - c[i]];

		}

	}

	LL ans = 0;

	for (LL i = 1; i < 16; i++)//枚举集合数1的个数

	{

		LL tmp = S, bit = 0;//1的个数

		for (LL j = 1; j <= 4; j++)

		{

			if ((i >> (j - 1)) & 1)//这一位1

			{

				tmp -= c[j] * (d[j] + 1);

				bit++;

			}

		}

		if (tmp >= 0)

			ans += (bit % 2 ? 1 : -1) * dp[tmp];//用容斥转化为无限制的完全背包情形

	}

	cout << dp[S] - ans << endl;

}

int main()

{

	IOS;

	for (int i = 1; i <= 4; i++)

		cin >> c[i];

	cin >> N;

	for (int i = 0; i < N; i++)

	{

		for (int j = 1; j <= 4; j++)

			cin >> d[j];

		cin >> S;

		solve();

	}

	return 0;

}

巴特西

洛谷P1450.硬币购物

最新文章

热门文章