钱币兑换问题（母函数）

超、凢脫俗 2022-08-02 14:52 200阅读 0赞

# 钱币兑换问题 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 7461    Accepted Submission(s): 4403**

Problem Description

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input

每行只有一个正整数N，N小于32768。

Output

对应每个输入，输出兑换方法数。

Sample Input

2934
    12553

Sample Output

718831
    13137761

Author

SmallBeer(CML)

Source

[杭电ACM集训队训练赛（VII）][ACM_VII]

**原来母函数只需要一次遍历就能得到1-n范围里面的答案，我以为需要·每一次遍历呢？**

**学习了！**

#include<cstdio>
    #include<iostream>
    #include<cstring>
    const int N=32770;
    using namespace std;
    int a[N],b[N],num[N];
    int main()
    {
        int i,j,k,n,f;
        for(i=0;i<=N;i++)
        {
            a[i]=1;
            b[i]=0;
        }
        for(i=2;i<=3;i++)
        {
            for(j=0;j<=N;j++)
            {
                for(k=0;k+j<=N;k+=i)
                {
                    b[j+k]+=a[j];
                }
            }
            for(j=0;j<=N;j++)
            {
                a[j]=b[j];
                b[j]=0;
            }
        }
        while(scanf("%d",&n)!=EOF)
        {
            printf("%d\n",a[n]);
        }
    }

[ACM_VII]: http://acm.hdu.edu.cn/search.php?field=problem&key=%BA%BC%B5%E7ACM%BC%AF%D1%B5%B6%D3%D1%B5%C1%B7%C8%FC%A3%A8VII%A3%A9&source=1&searchmode=source

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关 2023华为OD面试手撕真题【钱币兑换问题】

来自2023年11月牛客网的网友分享的面经：[华为od面经分享\_牛客网][od] ![6ea5d38f84bc443f80d2ff196fb55f5c.png][] 题目

缺乏、安全感/ 2024年02月18日 11:48/ 0 赞/ 55 阅读

相关钱币兑换问题（完全背包）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

￡神魔★判官ぃ/ 2022年08月02日 14:53/ 0 赞/ 213 阅读

相关钱币兑换问题（母函数）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

超、凢脫俗/ 2022年08月02日 14:52/ 0 赞/ 201 阅读

相关钱币找零问题

钱币找零问题这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6

待我称王封你为后i/ 2022年06月18日 04:20/ 0 赞/ 255 阅读

相关 hdu 1284 钱币兑换问题

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

客官°小女子只卖身不卖艺/ 2022年05月31日 09:44/ 0 赞/ 168 阅读

相关母函数

int a[1001],b[1001]; int v[201],n1[201],n2[201]; / Function:

逃离我推掉我的手/ 2022年05月28日 12:57/ 0 赞/ 221 阅读

相关 A - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

爱被打了一巴掌/ 2022年03月07日 15:22/ 0 赞/ 195 阅读

相关 G - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

我不是女神ヾ/ 2022年02月24日 06:52/ 0 赞/ 256 阅读

相关母函数

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] 学了好长时间母函数了，一直没时间进行总结（忙于一些琐事），今天正好放一

冷不防/ 2022年01月15日 10:11/ 0 赞/ 225 阅读

相关 HDU 1284 钱币兑换问题

include<cstdio> include<cstring> include<cmath> include<algorithm> u

落日映苍穹つ/ 2021年12月22日 11:39/ 0 赞/ 178 阅读