BZOJ1042 [HAOI2008]硬币购物【完全背包 + 容斥】

2022-10-28 15:34:07

1042: [HAOI2008]硬币购物

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2924 Solved: 1802

[Submit][Status][Discuss]

Description

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s

i的价值的东西。请问每次有多少种付款方法。

Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

　　每次的方法数

Sample Input

1 2 5 10 2

3 2 3 1 10

1000 2 2 2 900

Sample Output

4

27

首先我们一次次做背包肯定T

考虑一次性做完完全背包，每次减去不合法的方案数

显然每次 ans = f[s] - 第一样物品超过限制的方案数 - 第二样物品超过限制的方案数 - 第三样物品超过限制的方案数 - 第四样物品超过限制的方案数 + 第一二样物品超过限制的方案数 + .......

具体超过限制的方案数怎么求？以第一个物品为例，就是f[s - (d[i] + 1) * c[i]]，就是我们先用上d[i] + 1个硬币，剩余的部分任意取，所得的方案数就是我们所求

这算法太巧妙了> <

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define fo(i,x,y) for (int i = (x); i <= (y); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline LL read(){

	LL out = 0,flag = 1;char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}

	return out * flag;

}

LL f[maxn],C[5],d[5],S;

void cal(){

	f[0] = 1;

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

		for (int j = C[i]; j <= 100000; j++)

			f[j] += f[j - C[i]];

}

int main()

{

	REP(i,4) C[i] = read();

	cal();

	int T = read();

	LL ans,flag,sum;

	while (T--){

		REP(i,4) d[i] = read(); S = read();

		ans = f[S];

		for (int s = (1 << 4) - 1; s > 0; s--){

			sum = 0; flag = 1;

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

				if ((1 << i - 1) & s){

					sum += (d[i] + 1) * C[i];

					flag = -flag;

				}

			if (sum <= S) ans += flag * f[S - sum];

		}

		printf("%lld\n",ans);

	}

	return 0;

}

码农公寓