Luogu – P1450 – [HAOI2008]硬币购物

题意

题目链接

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚第 $i$ 种硬币,想购买价值恰好为 $s$ 的东西。

多次询问,每次询问形如 $(d_1,d_2,d_3,d_4,s)$,求付款方法数。

$1\leq c_i,d_i,s\leq 10^5$,$1\leq n\leq 1000$.

题解

先不考虑硬币个数限制,用 $f_i$ 表示随意凑出 $i$ 元的方案数,预处理出 $f$.

对每个硬币背包转移,若四种硬币面额为 $c_1,c_2,c_3,c_4$,则:

$$
f_i=\sum_{j=1}^{4}f_{i-c}
$$

再看硬币个数的限制。

 

如果只有一种面值为 $c$ 的硬币,限制最多用 $d$ 枚,想要凑出 $s$ 元。

相较于所求,$f_s$ 中多余的部分,就是取出了至少 $(d+1)$ 枚硬币。

根据 $f_s$ 的定义可知,取至少 $(d+1)$ 枚硬币后凑出 $s$ 的方案数为 $f_{s-c\times(d+1)}$.

可以理解为:先花掉 $(d+1)$ 枚硬币,剩下随便凑。

所以只有一种硬币时,$\operatorname{Ans}=f-f_{s-c\times(d+1)}$.

 

现在就可以开始解决本题中四种硬币的情况了,也是同样的思路,考虑容斥

$$
f[s]-\sum_{i=1}^{4}f[s-c_i\times (d_i+1)]
$$

直接这样减下去,同时不满足两个硬币的情况会重复,要加回来。

依次类推,同时不满足三个条件的要减下去,同时不满足四个的要加回来。

这个过程可以用二进制枚举方便地解决。

代码

const int N = 1e5;
int n, c[4], d[4], s, ans;
int f[N + 10]; //f[s]表示:四种面值随便取,取出s的方案数量
signed main() {
	cin >> c[0] >> c[1] >> c[2] >> c[3] >> n;
	f[0] = 1;
	for(int i = 0; i < 4; i++) {
		for(int j = c[i]; j <= N; j++) {
			f[j] += f[j - c[i]];
		}
	}
	for(int i = 1; i <= n; i++) {
		cin >> d[0] >> d[1] >> d[2] >> d[3] >> s;
		ans = 0;
		for(int sta = 0; sta < (1 << 4); sta++) {
			int cnt = 0, sum = 0;
			for(int k = 0; k < 4; k++) {
				cnt ^= (1 & (sta >> k));
				sum += (1 & (sta >> k)) * c[k] * (d[k] + 1);
			}
			if(s - sum >= 0)
				ans += f[s - sum] * (cnt ? -1ll : 1ll);
		}
		cout << ans << endl;
	}
	return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇