BZOJ1042 [HAOI2008]硬币购物 【dp+容斥原理】

tonyfang posted @ 2016年5月05日 21:34 in BZOJ with tags c++ oi , 321 阅读

题解:

首先我们发现直接做有点坑

考虑没有数量限制的

f[i]表示表示i有多少种方法

然后如果要满足限制,就是减去限制+1的个数,容斥即可,十分神奇。

 

# include <stdio.h>
using namespace std;

int c[5], tot;
long long  f[100010];
int a[5], s;
long long ans=0;

inline void dfs(int x, int num, int sum) {
	if(sum<0) return;
	if(x==5) {
		if(num%2 == 1) ans -= f[sum];
		else ans += f[sum];
		return ;
	}
	dfs(x+1, num+1, sum-(a[x]+1)*c[x]);
	dfs(x+1, num, sum);
}

int main() {
	
	scanf("%d%d%d%d%d", &c[1], &c[2], &c[3], &c[4], &tot);
	
	f[0] = 1;
	for (int i=1; i<=4; ++i)
		for (int j=c[i]; j<=100000; ++j)
				f[j] += f[j-c[i]];
	
	while(tot--) {
		scanf("%d%d%d%d%d", &a[1], &a[2], &a[3], &a[4], &s);
		ans=0;
		dfs(1, 0, s);
		printf("%lld\n", ans);
	}
	
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter