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

￡神魔★判官ぃ 2022-08-02 14:53 225阅读 0赞

# 钱币兑换问题 #

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

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]

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    const int N=32770;
    using namespace std;
    int dp[N];
    int main()
    {
        int n,i,j;
        while(cin>>n)
        {
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            for(i=1;i<=3;i++)
            {
                for(j=i;j<=n;j++)
                {
                    dp[j]=dp[j-i]+dp[j];
                }
            }
            cout<<dp[n]<<endl;
        }
    }

[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 条评论，225人围观）

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

相关阅读

相关动态规划-完全背包问题（纯完全背包、零钱兑换II、组合总数 IV、零钱兑换、完全平方数、单词拆分）、纯多重背包问题

1.完全背包问题（每件物品可放多次）有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品都有无

迈不过友情╰/ 2023年09月25日 18:30/ 0 赞/ 51 阅读

相关 518 零钱兑换 II（完全背包问题）

1. 问题描述：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑

系统管理员/ 2022年08月30日 04:12/ 0 赞/ 265 阅读

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

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

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

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

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

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

相关完全背包问题

1. 问题描述有 N 种物品, 物品 i 的重量为 wi, 价格为 vi, 背包所能承受的最大重量为 W。其中, N,W,wi,vi≥0 若每种物品仅有一件,

短命女/ 2022年07月12日 06:37/ 0 赞/ 215 阅读

相关 hdu 1284 钱币兑换问题

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

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

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读

相关 A - 钱币兑换问题

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

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

相关 G - 钱币兑换问题

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

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

相关 HDU 1284 钱币兑换问题

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

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