首页 > 代码库 > BZOJ1042 [HAOI2008]硬币购物

BZOJ1042 [HAOI2008]硬币购物

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

 

 

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

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

 

 

正解:DP+容斥原理

解题报告:

  这题显然爆搜没救QAQ

  考虑我们如果直接$DP$的话无法保证不超过限制,那么对于这种有限制的问题,我们可以很快想到用容斥原理。
  先预处理出不含限制的情况下的方案数,再想想如何处理限制。

  根据容斥的惯用思路,都是对于若干限制,满足其中一些,然后根据奇偶性进行判断。

  所以我们只要用全集$-$打破$1$个限制的方案$+$打破$2$个的$-$打破$3$个的$+$打破$4$个的,即可得到满足要求的答案。

  考虑如何求出打破特定个限制的方案数,我们先枚举打破哪些限制,再强制其买$d[i]+1$个,就可以保证已经打破,剩下的就是无限制的情况了。

  只需对于每次询问都$2^4$处理一次就可以了。  

 

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 100011;
int c[12],m,d[12],n;
LL f[MAXN],ans;

inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void dfs(int x,int remain,int num){
	if(x==5) {
		if(num&1) ans-=f[remain];
		else ans+=f[remain];
		return ;
	}
	int now=c[x]*(d[x]+1);
	if(remain>=now) dfs(x+1,remain-now,num+1);
	dfs(x+1,remain,num);
}

inline void work(){
	for(int i=1;i<=4;i++) c[i]=getint(); 
	m=getint(); f[0]=1;
	//为避免方案重复计算,必须按不同种类的硬币划分阶段!
	for(int j=1;j<=4;j++) {
		for(int i=1;i<=100000;i++) {		
			if(i<c[j]) continue;
			f[i]+=f[i-c[j]];
		}
	}
	while(m--) {
		for(int i=1;i<=4;i++) d[i]=getint(); n=getint();
		ans=0;
		dfs(1,n,0);
		printf("%lld\n",ans);
	}
}

int main()
{
    work();
    return 0;
}

  

BZOJ1042 [HAOI2008]硬币购物