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)减去不
一周排行
  • .net 面向對象程序設計進階 (16) 多線程(Multithreading)(一) 利用多線程提高程序效能(上)
    [.net 面向对象程序设计进阶] (16) 多线程(Multithreading)(一) ...
  • 使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的openjdk,那么到底什么是openjdk,它与sun jdk有什么关系和区别呢? 历史上的原因是,open ...
  • package com.example.user_defined_view; import android.app.Activity;import android.os.Bundle;import android.v
  • JWFD開源專案官方網站預覽
    自己做的...感觉还比较正规哈....JWFD开源项目还是需要一个官方网站的...
  • 转自通九大神的博客   起因 最近公司RabbitMQ的集群出了点问题,然后有些亲就说RabbitMQ慢且不好用,是一个瓶颈,不如换成Kafka.而我本人,使用RabbitMQ有一点久了,认为这个事情应当辩证的去看.
  • 继承 C#中,创建派生类要在派生类的名字后面加上冒号,后面再跟上基类的名字: 1 public class ListBox : Control 提示:C++程序员注意了,C#没有私有或者保护继承 多态 继承又两个功能
  • 一.动画类型 Android的animation由四种类型组成:alpha.scale.translate.rotate XML配置文件中 alpha 渐变透明度动画效果 scale 渐变尺寸伸缩动画效果 trans ...
  • ORACLE 10G RAC for Linux AS4 安装 以前写的一篇关于RAC的帖子,收录在这里... ==================================================== ...
  • 1,安装:需要下面两个包 bind-9.3..P1.el5.i386.rpm bind-chroot-9.3..P1.el5.i386.rpm 2,安装成功后,Bind9的程序目录存放在/var/name
  • C:有点这种题的经验,先存起来相等的 D:赛后还搓了好久的代码,其实长度就100,枚举两边情况,其实A和C就涵盖了所有情况!所以到2就可以了,而且我弄出了有多少个后,和两边情况,也不知道能否或怎么凑成串! - -,然