BZOJ 1042: [HAOI2008]硬币购物 (详解)
程序员文章站
2022-04-28 10:19:57
题面:https://www.cnblogs.com/fu3638/p/6759919.html 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西, 请问每次有多少种付款方法。其中di,s<=100000,tot<=1 ......
题面:https://www.cnblogs.com/fu3638/p/6759919.html
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西,
请问每次有多少种付款方法。其中di,s<=100000,tot<=1000。
题解:
首先考虑一个简单的问题,如果去掉题目中对于个数的限制,即给你四种面值的的硬币,问你有多少种方案能凑成
si的价值。欸我们瞬间发现这是个完全背包的裸题,那果断乱搞。
首先我们做一遍完全背包,定义f[i]为凑成i价值的方案数。
接下来回到原题,我们发现题目加了一个di的限制,那怎么办呢(摸摸脑袋)。
经过冷静的分析(查题解),发现这题可以用容斥原理乱搞。
通过容斥原理,我们得出ans=全部方案(不考虑限制(即f[ans]))-Σ一种面值超过限制的方案数+Σ两种超限-Σ三种超限+Σ四种超限。
那么如何求有几种超过限制的方案数呢
以一种面值超过限制的方案数为例,那么这一种(不妨设为第i种)至少用d[i]+1个,即产生c[i]*(d[i]+1)的价值。那么剩下的s-c[i]*(d[i]+1)(记为rest)
就可以随意取值,即为f[rest]种。
那么两种三种的就是f[rest](rest=s-Σc[i]*(d[i]+1))。
tip:枚举方案可以用位运算。
P.S. 开long long!!
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxs=100000; ll ans,f[maxs+10]; int c[5],d[5],tot,s; 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<=maxs;j++) f[j]+=f[j-c[i]]; for(int k=1;k<=tot;k++){ scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s); ans=0; for(int i=0;i<(1<<4);i++){ int rest=s,tt=i,num=0,pos=0; while(tt){ pos++;//第几枚硬币 if(tt&1) rest-=c[pos]*(d[pos]+1),num++;//num->几枚有限制 tt>>=1; } if(rest<0) continue; if(num&1) ans-=f[rest]; else ans+=f[rest]; } printf("%lld\n",ans); } return 0; }
参考:
https://blog.csdn.net/aarongzk/article/details/51511564
https://blog.csdn.net/doctor_godder/article/details/50071749