BZOJ1042DP + 容斥HAOI2008硬币购物

Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

1 2 5 10 2
3 2 3 1 10
1 2 2 2 900

Sample Output

4
27

HINT

数据规模
di,s<=100
tot<=1

【分析】

不是数学吗?容斥也算数学吧...

进行一下预处理,求出在可以任取硬币的条件下f(i) 为取得价值为i的方案总数。

然后容斥用总超过限制-1超过限制-2超过限制-3超过限制-4超过限制+1、2超过限制...

怎么算1超过限制?设s为总价值,1的限制量为d[i],价值为c[i],则1超过限制量为f[s - (d[i] + 1) * c[i]]。

代码复杂度很低,不写了。

更多相关文章
  • 1042: HAOI2008硬币购物
    Description硬币购物一共有4种硬币.面值分别为c1,c2,c3,c4.某人去商店买东西,去了tot次.每次带di枚ci硬币,买si的价值的东西.请问每次有多少种付款方法.Input第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,sOutput每次的方法数Sam ...
  •   Lengthening Sticks Problem's Link:  http://codeforces.com/contest/571/problem/A   Mean:  给出a,b,c,l,要求a+x,b
  • 容斥+javaSGU 476 Coachs Trouble
    通道 题意:有3*n个人,分成n组,每组三个人.给出k个三元组,这三个人不可组队,问最后可
  • 给10^5个操作,每次操作添加或删除一个不超过10^5的正整数,问当前存在的数两两之间互质的对数. 一下就确定是根据添加的数的约数来处理,但是不好排除重复计算的,只想到最土的一次操作是该数的约数个数平方级别的做法.看了别人代码才知道,是最原始的容斥,根据包含的素因子的个数来.比如12有两个素因子2,
  • 题目大意: 求x属于[1,b]和 y属于[1,d]的 gcd(x,y)=k 的方案数 题解: 观察发现 gcd()=k 不好处理,想到将x=x/k,y=y/k 后 gcd(x,y)=1.. 即问题转化为求区间 [1,
  • cf#305  Mike and Foam(容斥)
    C. Mike and Foam time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Mike is a bartender at ...
  • HUST 1569(Burnside定理+容斥+數位dp+矩陣快速冪)
      传送门:Gift 题意:由n(n<=1e9)个珍珠构成的项链,珍珠包含幸运数字(有且仅由4或7组成),取区间[L,R]内的数字,相邻的数字不能相同,且旋转得到的相同的数列为一种,为最终能构成多少种项链. 分析:这是我做过的最为综合的一道题目(太渣了),首先数位dp筛选出区间[L,R]内的幸 ...
  • 现场过的第四多的题..当时没什么想法,回来学了下容斥,又听学长讲了一讲,终于把它过了 题目大意:给定n个数,求全部互质或者全部不互质的三元组的个数 先说一下同色三角形模型 n个点 每两个点连一条边(可以为红色或者黑色),求形成的三条边颜色相同的三角形的个数 反面考虑这个问题,只需要c(n,3)减去不
一周排行
  • [故障现象]用groupdel删除test组时,报以上错误.原因为test组中有lxh1用户(lxh1的主组). [解决辦法]更改lxh1的主组后即可删除. root@oldboy ~$tail -n 2 /etc/
  • QTime Class Reference [QtCore module] QTime类提供时间函数 #include <QTime> 注意:所有函数是可重入的 公共函数: QTime() QTime(i ...
  • 摘要: : 使用函数:substr(列,开始字符,截取长度) 第1个参数是列,第1列是$0,第2列是$1,..... 第2个参数是开始字符,从1开始 第3个参数是截取的长度 $echo "123456789 ...
  • 使用Visual Studio 2010打造C語言編譯器
           相信学习C语言的同学们一直在为自己的windows7不能用vc 6.0而烦恼
  • 奇怪吸引子QiChen
          奇怪吸引子是混沌学的重要组成理论,用于演化过程的终极状态,具有如下特征:终极性
  • http://os.51cto.com/speclist/1366/list_1366_5.htm http://os.51cto.com/art/200712/62180.htm http://os.51cto.c
  • 9 7 题目:对于8x8的棋盘,如果拿掉对角位置的两个小块儿,能否用1x2的多米诺牌拼成剩下的棋盘? 解法:不可能.且不说8x8,NxN都是不可能的.如果N是奇数,NxN-2是奇数,自然不可
  • Ctrl+1 快速修复(最经典的快捷键,就不用多说了)Ctrl+D: 删除当前行Ctrl+Alt+ 当前行到下一行(增加)Ctrl+Alt+ 当前行到上一行(增加)Alt+ 当前行和下面一行交互位置(特别实用,可以省
  • lightoj 1179(線段樹)
      传送门:Josephus Problem 题意:经典约瑟夫问题,有n个人,每次数到第k ...
  • 在做asp.net和unity进行http通信的时候,当unity客户端发出表单请求的时候,我要将他要请求的数据以json的格式返回给客户端,让客户端来解析.服务器端这一块就涉及到json的序列化和反序列化的问题. ...