[UVa] 674 Coin Machine.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
int method[10000] = {0};
int cent[5] = {1, 5, 10, 25, 50};
int main()
{
    // 建表
    method[0] = 1;
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j + cent[i] <= 7490; ++j)
            method[j+cent[i]] += method[j];
    }
    // input & output
    int n;
    while (scanf("%d", &n) != EOF)
        printf("%d\n", method[n]);
}