http://acm.hdu.edu.cn/showproblem.php?pid=2069

Problem Description
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.
Input
The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.
Output
For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.
Sample Input
11 26
Sample Output
4 13 代码:
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int a[1111][1111];
int b[6]= {1, 5, 10, 25, 50};

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(a, 0, sizeof(a));
        a[0][0]=1;
        for(int j = 0; j <= 4; j ++)
        {
            for(int i = b[j]; i <= n; i ++)
            {
                for(int k = 1;k <= 100; k++)
                {
                    if(i >= b[j])
                        a[k][i] += a[k-1][i - b[j]];
                }
            }
        }
        int sum = 0;
        for(int i = 0; i <= 100; i ++)
        {
            sum += a[i][n];
        }
        printf("%d\n",sum);
    }
    return 0;
}

  

优质内容筛选与推荐>>
1、Javascript中NaN、null和undefinded的区别
2、Maven项目无法引入 Maven Dependencies Libraries 问题
3、(转载)设置TSK文件
4、CodeForces - 463D Gargari and Permutations
5、[Inno Setup] Do not show application version in “Program and Features” control panel


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn