[DP || 容斥] BZOJ1042: [HAOI2008]硬币购物

2019-11-06 09:06:29

字体：大中小

来源：转载

供稿：网友

题意

有4种硬币。面值分别为c1, c2, c3, c4。 Q组询问，每次给出4种硬币的使用个数上限limit_i,以及一个数S，求组合出S的总面值的满足限制条件的方案数。 di,S<=100000, Q<=1000

题解

注意到硬币个数对于所有询问是固定的，且个数很少，所以我们肯定需要预处理一些东西。先不考虑硬币个数的限制，刷一次普通的背包得到f[i]，表示用4种硬币组合出i的总面值的方案数。显然对于每次询问，ans=f[S]-{不合法的方案数}。我们怎样求不合法的方案数呢？对于第i种硬币超出限制的方案，可以很容易求得 f[S−(limit[i]+1)∗c[i]] $f[S-(limit[i]+1)*c[i]]$ ，即取limit[i]+1个，剩下的随便取。但是我们不能直接简单的把4个值相加，因为有重复部分，可能有两种硬币都超出，或3种、4种。硬币只有4种，所以直接暴力容斥即可求出他们的并。~~说的我好像做过不暴力的容斥题目一样~~

#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;const int maxn=100005;int n,allv,Q,w[10],a[10];LL f[maxn],ans;void In_Ex_clusion(int step,int k,int now){ if(now<0) return; if(step>4){ if(k&1) ans-=f[now]; else ans+=f[now]; return; } In_Ex_clusion(step+1,k,now); In_Ex_clusion(step+1,k+1,now-(a[step]+1)*w[step]);}int main(){ freopen("bzoj1042.in","r",stdin); freopen("bzoj1042.out","w",stdout); for(int i=1;i<=4;i++) scanf("%d",&w[i]); f[0]=1; for(int i=1;i<=4;i++) for(int j=w[i];j<=100000;j++) f[j]+=f[j-w[i]]; scanf("%d",&Q); while(Q--){ for(int i=1;i<=4;i++) scanf("%d",&a[i]); int S; scanf("%d",&S); ans=0; In_Ex_clusion(1,0,S); PRintf("%lld/n",ans); }}

上一篇：ubuntu 16.04 卸载旧网卡noveau装新的网卡驱动

下一篇：Eclipse中SVN插件安装附带资源

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注