HDU/HDOJ 2152 Fruit(上下界母函数)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2152

上下界母函数,没什么特别的,理解了母函数就可以OK~~~

母函数详解:http://www.wutianqi.com/?p=596

不过有一点要注意,我只把c2全部初始化为0,而c1我只把least和most的范围初始化为1,而忘了把其余部分初始化为0,这样就导致了一直WA~~~

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 2152 Fruit
// About: 母函数
 
#include <iostream>
using namespace std;
 
int N, M;
//int A, B;
int a[105], b[105];
int c1[105], c2[105];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> N >> M)
    {
        //cin >> A >> B;
        for(int i=1; i<=N; ++i)
            cin >> a[i] >> b[i];
        memset(c2, 0, sizeof(c2));
        memset(c1, 0, sizeof(c1));   // 这里害我找了一个小时的错误
        for(int i=a[1];i <=b[1]; ++i)
            c1[i] = 1;
        for(int i=2; i<=N; ++i)
        {
            for(int j=0; j<=M; ++j)
                for(int k=a[i]; (k+j<=M) && (k<=b[i]); ++k)
                    c2[k+j] += c1[j];
            for(int j=0; j<=M; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << c1[M] << endl;
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 2152 Fruit(上下界母函数)》有9个想法

  1. 大神, 这句 for(int i=a[1];i <=b[1]; ++i)
    c1[i] = 1;
    为什么只初始化a[1]到b[1],其他的a[2]….a[n]不用像a[1]那样初始化吗?

  2. Mr.Woo~

    这里,

    for(int k=a[i]; (k+j<=M) && (k<=b[i]); ++k)

    为什么++k改成k+=i最后结果就变成组合数了(即把M拆分成满足题意中上下界的拆分数)?

    1. 而为什么++k(或k++)最后结果就变成了所需要的排列数(即把M拆分成满足题意中上下界拆分情况的排列数)?

        1. 在我给的母函数模版是,使用到的例子是: 有不同面值的硬币,求面值组合的方案。而这里的实际情况是:有不同种水果,但是你需要把他们每种的价值都当作1,因为题目求的是总个数,而硬币那个情况是求的不同面值总和的面值

发表评论

电子邮件地址不会被公开。 必填项已用*标注