题目

Description

我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。

Input

输入有多组，每组一行，为一个整合n。
输入以0结束。

Output

输出该面额有几种表示方法。

Sample Input

1
4
0

Sample Output

1
3

题解

类似于>AOJ 808.算法期末考试D(整数拆分)<
最初想用完全背包问题求解,不过由于还要保证使用的钱数不超过 100 ,可以用 DFS 来计算

由于只有 1~205 ,可以使用打表法来输出

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int money[] = {1,2,5,10,20,50,100};

const int ans[] = {0,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34,41,44,51,54,61,68,75,82,89,96,109,116,129,136,149,162,175,188,201,214,236,249,271,284,306,328,350,372,394,416,451,473,508,530,565,600,635,670,705,740,793,828,881,916,969,1022,1075,1128,1181,1234,1311,1364,1441,1494,1571,1648,1725,1802,1879,1956,2064,2141,2249,2326,2434,2542,2650,2758,2866,2974,3121,3229,3376,3484,3631,3778,3925,4072,4219,4366,4563,4709,4905,5051,5247,5442,5637,5832,6027,6221,6476,6669,6924,7116,7369,7622,7875,8127,8378,8628,8954,9202,9526,9772,10094,10415,10735,11054,11371,11686,12093,12406,12810,13119,13520,13920,14318,14713,15106,15497,15998,16384,16880,17262,17754,18243,18729,19212,19692,20169,20776,21246,21847,22311,22905,23495,24081,24663,25240,25812,26539,27103,27821,28375,29083,29786,30483,31174,31859,32538,33398,34065,34913,35567,36401,37228,38048,38859,39662,40458,41465,42245,43234,43997,44970,45933,46885,47828,48762,49686,50851,51754,52899,53781,54903,56013,57111,58197,59271,60332,61671,62705,64018,65026,66309,67578,68833,70073,71296,72503,74029,75206,76699,77839,79297,80738,82159,83562,84944,86308,88035,89360,91045,92327,93970,95593,97191,98768,100318,101850,103791,105272,107162,108595,110434,112250,114034,115795,117525,119231,121396,123044,125152,126740,128786,130806,132787,134743,136660,138547,140953};

int v;

int num;
void DFS(int a,int pos,int cnt) {
    if(a < 0 || cnt>100)
        return;
    if(a == 0 ) {
        num++;
        return;
    }
    int tMoney = money[pos];

    if(pos < 0)
        return;

    for(int j = a / tMoney;j >= 0;j--) {
        DFS(a - j * tMoney,pos - 1,cnt + j);

    }
}

bool  Do() {
    scanf("%d",&v);
    if(v == 0)
        return false;
    /*
    num = 0;
    DFS(v,sizeof(money) / sizeof(int) - 1,0);

    printf("%d\n",num);
    */
    printf("%d\n",ans[v]);
    return true;
}

int main() {
    /*
    for(int i = 1;i <= 250;i++) {
        num = 0;
        DFS(i,sizeof(money) / sizeof(int) - 1,0);
        printf("%d,",num);
    }
    */
    while(Do());
    return 0;
}