洛谷P1450 [HAOI2008]硬币购物（背包问题，容斥原理）

洛谷题目传送门

我实在是太弱了，第一次正儿八经写背包DP，第一次领会如此巧妙的容斥原理的应用。。。。。。

对每次询问都做一遍多重背包，显然T飞，就不考虑了

关键就在于每次询问如何利用重复的信息

我这么弱，当然是想不到容斥原理的啦

暂且先当成完全背包，每种硬币可使用无限次，预处理\(f\)数组，\(f[i]\)等于买价值\(i\)的东西的总方案数

然后就要从中减去不合法的。首先肯定会有一种硬币超额使用，第\(j\)中硬币等于说强制选了\(d_j+1\)个，剩下的依然随便选，那么第

\(j\)种硬币超额的不合法的方案数等于\(f[s-(d_j+1)*c_j]\)，于是从答案里减去\(\sum_{j=1}^4f[s-(d_j+1)*c_j]\)

还要注意，第一种第二种都超额、第一种第三种都超额、第一种第四种都超额、第二种第三种都超额、第二种第四种都超额、第三种第四种都超额的方案在上一步中都被减了两次，所以额外都加一次回来。。。。。。（接着把容斥做下去就不说了）

复杂度降到\(O(4maxs+4×2^4tot)\)，轻松通过

注意开longlong就好啦

#include<cstdio>

#define R register

typedef long long LL;

const int S=100009;

LL f[S]={1ll};

int main(){

	R int c[4],d[4],tot,i,j,k,now,s,ss,tmp;

	R LL ans;

	for(j=0;j<4;++j)scanf("%d",&c[j]);

	scanf("%d",&tot);

	for(j=0;j<4;++j)

		for(i=c[j];i<S;++i)

			f[i]+=f[i-c[j]];//完全背包预处理

	while(tot--){

		for(j=0;j<4;++j)scanf("%d",&d[j]);

		scanf("%d",&s);

		ans=f[s];

		for(ss=1;ss<=15;++ss){//二进制数枚举集合，容斥

			now=s;

			for(tmp=ss,j=k=0;tmp;tmp>>=1,++j)

				if(tmp&1)k^=1,now-=(d[j]+1)*c[j];

                //注意k的作用，判断奇偶

			if(now>=0)k?ans-=f[now]:ans+=f[now];

		}

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

	}

	return 0;

}

巴特西

洛谷P1450 [HAOI2008]硬币购物（背包问题，容斥原理）

最新文章

热门文章