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)减去不
一周排行
  • 1.char* 转换成 LPCTSTR char ch[1024] = "wo shi ni baba"; int num = MultiByteToWideChar(0,0,ch,-1,NULL ...
  • WebGL开启了网页3D渲染的新时代,它允许在canvas中直接渲染3D的内容,而不借助任何插件.WebGL同canvas 2D的API一样,都是通过脚本操纵对象,所以步骤也是基本相似:准备工作上下文,准备数据,在c ...
  • 抛出錯誤Debug Assertion Failed!
    出现这种情况很可能是使用了野指针,比如某个指针指向一个局部变量,而在该变量作用域外使用该指 ...
  • 腦洞大開加偏執人格——可持久化treap版的Link Cut Tree2
    试了一下先上再下的Treap方式,很高兴,代码变短了,但是,跑的变慢了!!!其实慢得不多,
  • 最近使用ajax调用一般处理程序时,出现外网调用不成功,内网调用成功,错误码为12030或12301的情况.当时在网上搜索了一些资料,有的说是因为文件中取了个中文名称导致的,有的是说要配置什么IIS之类的.最后在防火
  • 概述:公司有一些核心MYSQL服务器位于核心机房的内网段,作为运维人员,经常需要去连接这些服务器,因无法直接通过外网访问,给管理造成了不便. 思路:虽然解决此问题的方法及思路有很多,但当下想使用IPTABLES的端口 ...
  •     #import "ViewController.h"@interface ViewController () @end @implementation ViewController - ( ...
  • 1.源码安装MySQL 5.1 GA 创建组和用户: [[email protected] ~]# groupadd mysql [[email protected] ~]# useradd -g mysql mysql 解压缩安装
  • “Uncaught TypeError: string is not a function”
    http://www.cnblogs.com/haitao-fan/archive/201
  • 题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1278 这道题需要用到两个姿势第一将圆相离的模型转换成线段和线段之间不想交,然后