hdu 2069

这题一看，用动态规划、母函数应该都可以，我用深搜水过~

/*
 * hdu2069/linux.c
 * Created on: 2011-7-28
 * Author    : ben
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int kind;
int money[5] = {50,25,10,5,1};
int num[5];

void dfs(int step, int remainmoney) {
    int i, temp = 0;
    if(step == 4) {
        for(i = 0; i < step; i++) {
            temp += num[i];
        }
        if(temp + remainmoney <= 100) {
            kind++;
        }
        return ;
    }
    num[step] = 0;
    do{
        dfs(step + 1, remainmoney - num[step] * money[step]);
        num[step]++;
    }while(num[step] * money[step] <= remainmoney);
}

void work();
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    work();
    return 0;
}

void work() {
    int totalmoney;
    while(scanf("%d", &totalmoney) != EOF) {
        kind = 0;
        dfs(0, totalmoney);
        printf("%d\n", kind);
    }
}