bzoj1042 硬币购物

74 阅读 0 评论 49 点赞

我是靠谱客的博主着急八宝粥，最近开发中收集的这篇文章主要介绍bzoj1042 硬币购物，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

HINT

数据规模

di,s<=100000

tot<=1000

Source

dp+容斥原理

其实再就没什么写的了。。

代码短小精炼

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
ll ans,f[100005];
int T;
int c[5],d[5];
void dfs(int x, int y, int k)
{
	if(k < 0) return;
	if(x == 5)
	{
		if(y & 1) ans -= f[k];
		else ans += f[k];
		return;
	}
    dfs(x + 1, y + 1, k - (d[x] + 1) * c[x]);
	dfs(x + 1, y, k);
}

int main()
{
	for(int i = 1; i <= 4; i ++)
		c[i] = read();
	T = read();
	f[0] = 1;
	for(int i = 1; i <= 4; i ++)
		for(int j = c[i]; j <= 100000; j ++)
			f[j] += f[j - c[i]];
	for(int i = 1; i <= T; i ++)
	{
		for(int k = 1; k <= 4; k ++)
			d[k] = read();
		int x = read();
		ans = 0;
		dfs(1, 0, x);
		printf("%lldn",ans);
	}
	return 0;
}