专栏首页ACM算法日常水果Fruit(母函数) - HDU 2152

水果Fruit(母函数) - HDU 2152

转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 于是,很多人们慕名而来,找Lele买水果。 甚至连大名鼎鼎的HDU ACM总教头 lcy 也来了。lcy抛出一打百元大钞,"我要买由M个水果组成的水果拼盘,不过我有个小小的要求,对于每种水果,个数上我有限制,既不能少于某个特定值,也不能大于某个特定值。而且我不要两份一样的拼盘。你随意搭配,你能组出多少种不同的方案,我就买多少份!" 现在就请你帮帮Lele,帮他算一算到底能够卖出多少份水果拼盘给lcy了。 注意,水果是以个为基本单位,不能够再分。对于两种方案,如果各种水果的数目都相同,则认为这两种方案是相同的。 最终Lele拿了这笔钱,又可以继续他的学业了~

Input

本题目包含多组测试,请处理到文件结束(EOF)。 每组测试第一行包括两个正整数N和M(含义见题目描述,0<N,M<=100) 接下来有N行水果的信息,每行两个整数A,B(0<=A<=B<=100),表示至少要买该水果A个,至多只能买该水果B个。

Output

对于每组测试,在一行里输出总共能够卖的方案数。 题目数据保证这个答案小于10^9

Sample Input

2 3 
1 2 
1 2 
3 5 
0 3 
0 3 
0 3

Sample Output

2 
12

题意:

物品n种,每种数量分别为k1,k2,..kn个,每种物品又有一个属性值p1,p2,…pn,求属性值和为m的物品组合方法数。

生成函数(母函数)有普通生成函数和指数生成函数:

1.普通生成函数用于解决多重集的组合问题

2.指数型母函数用于解决多重集的排列问题

母函数可以解决递归数列的通项问题:斐波那契数列、卡特兰数列等

母函数利用的思想:

1.把组合问题的加法法则和幂级数的乘幂对应起来。

2.把离散数列和幂级数对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造

K对应具体问题中物品的种类数。

V[i]表示该乘积表达式第 i 个因子的权重,对应具体问题的每个物品的价值或者权重

n1[i]表示该乘积表达式第 i 个因子的起始系数,对应于具体问题中的每个物品的最少个数,即最少要取多少个

n2[i]表示该乘积表达式第i个因子的终止系数,对应具体问题中的每个物品的最多个数,即最多要取多少个

解题的关键是要确定V,N1,N2数组的值

AC代码

import java.util.*;
import java.math.*;

public class Main {
    public static int maxn=110;
    public static void main(String[] args) {
        int[] a=new int[maxn];//保存结果,a[i]表示组成i种水果的方案数为a[i]
        int[] b=new int[maxn];//中间结果
        int[] n1=new int[maxn];//第i种水果最少的个数
        int[] n2=new int[maxn];//第i种水果最多的个数
        int[] v=new int[maxn];//第i种水果的价值
        Scanner cin=new Scanner(System.in);

        //int T=cin.nextInt();
        while(cin.hasNext()) {
            for(int i=0;i<maxn;i++) {
                a[i]=0;b[i]=0;n1[i]=0;n2[i]=0;
                v[i]=1;
            }
            int n=cin.nextInt();
            int m=cin.nextInt();

            for(int i=1;i<=n;i++) {
                n1[i]=cin.nextInt();
                n2[i]=cin.nextInt();
            }

            a[0]=1;
            for(int i=1;i<=n;i++) {//循环每一个因子

                for(int k=0;k<maxn;k++)
                    b[k]=0;

                for(int j=n1[i];j<=n2[i]&&j*v[i]<=m;j++)//循环每个因子的每一项
                    for(int k=0;k+j*v[i]<=m;k++)//循环a的每一项
                        b[k+j*v[i]]+=a[k];//把结果加到对应的位

                for(int k=0;k<maxn;k++)//b赋值给a
                    a[k]=b[k];
            }
            System.out.println(a[m]);
        }
        cin.close();
    }
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:紫芝眉宇

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣 526.优美的排序(next_permutation?)

    链接:https://leetcode-cn.com/problems/beautiful-arrangement

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • Codeforces Round #549(div1)简析

    正解貌似有分四种情况什么的,我做时是发现各个起点其实都等价的,所以随便选一个起点,再暴举终点以暴举答案,更新即可。

    ACM算法日常
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩
  • 挖掘机技术哪家强(c++实现)

    描述:为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

    用户2038589
  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津
  • 15.瀑布流、测量

    六月的雨
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear

扫码关注云+社区

领取腾讯云代金券