题目描述

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.

输入

The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.


输出

For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

样例输入


11
26

样例输出


4
13

下面是程序：
#include<iostream>
using namespace std;
int main()
{
    int i,j,k,t;
    int nums[251]={0},coins[5]={1,5,10,25,50};
    int ans[251][101]={0},ansTemp[251][101]={0};
    //…[i][j]表示i分钱由j个硬币组成的方案数
    ans[0][0] = 1;

    for(i=1;i<=5;i++)
    {
        for(j=0;j<=250;j++)//这个循环的作用？
            for(k=0;k*coins[i-1]+j<=250;k++)//这里什么意思？。。
                for(t=0;t+k<101;t++)//总的硬币数要少于100//这个也不明白
                    ansTemp[k*coins[i-1]+j][t+k] += ans[j][t];
        for(j=0;j<=250;j++)
            for(t=0;t<101;t++)
            {
                ans[j][t] = ansTemp[j][t];
                ansTemp[j][t]=0;
            }
    }

    for(i=1;i<=250;i++)
        for(j=1;j<=100;j++)
            nums[i] += ans[i][j];
    nums[0] = 1;
    while(cin>>i)
        cout<<nums[i]<<endl;
    return 0;
}
主要说明一下循环的意思循环思想越详细越好。。。。很看不明白。。。。。谢谢。。

题目大意是有1分的5分的10分的25分的50分的钱，现在给你钱数N<=250分,问你有多少中不同的换发。。最主要的一点是兑换的总钱币数目不应超过100个，也就是说110分是不能换成103个一分的。。。

关于这题谁来看下?.!!>>>.

要一直刷新到有人来看。。。

上网搜搜DP。

先考虑看懂下面的程序吧：

#include <stdio.h>
#include <stdlib.h>
/* [i][j][k]表示当仅仅使用前i+1种硬币的时候，j分钱由k个硬币组成的方案数 */
int ans[5][251][101] = {{0}};                             
int nums[251] = {0};
int coins[5] = {1, 5, 10, 25, 50};
int main(void)
{
    int i, j, k, l;
    /* 首先，当仅仅使用前一种硬币（一分的）时候，显然i分钱只能由i个硬
     * 币组成，而且方案仅此一种。 */
    for (i = 0; i <= 100; ++i)
        ans[0][i][i] = 1;
    /* 现在我们考虑i等于1到4的情况（即2到5种硬币） */
    for (i = 1; i < 5; ++i)
    {
        /* 我们枚举一下单纯这一种硬币组成的情况 */
        for (j = 0; j * coins[i] <= 250; ++j)
        {
            /* 在这种情况下，每一种前一种的方案，我们都可以用新的硬币
             * 代替，从而获得新的方案，以下就是枚举旧的方案，产生新的
             * 方案的数量的过程 */
            for (k = 0; j * coins[i] + k <= 250; ++k)
                for (l = 0; j + l <= 100; ++l)
                    ans[i][j * coins[i] + k][j + l] += ans[i - 1][k][l];
        }
    }
    /* 最后汇总 */
    for (i = 1; i <= 250; ++i)
        for (j = 1; j <= 100; ++j)
            nums[i] += ans[4][i][j];
    while (scanf("%d", &i) != EOF)
        printf("%d\n", nums[i]);
    return 0;
}

这种程序写注释，ls真有时间

谁能再注释下我的程序谢谢了。。。。

...............

我的确是太有时间了，而且还被无视了……还是无视掉我吧……