uva 357 Let Me Count The Ways(01背包）

题目连接：357 - Let Me Count The Ways

题目大意：有5种硬币， 面值分别为1、5、10、25、50，现在给出金额，问可以用多少种方式组成该面值。

解题思路：和uva674是一样的， 只是上限不一样， 还有注意下输出。

#include <stdio.h>#include <string.h>const int N = 30005;const int val[5] = {1, 5, 10, 25, 50};long long cnt[N];void Init() { memset(cnt, 0, sizeof(cnt)); cnt[0] = 1; for (int i = 0; i < 5; i++) {for (int j = val[i]; j < N; j++) cnt[j] += cnt[j - val[i]]; }}int main() { Init(); int n; while (scanf("%d", &n) == 1) {if (cnt[n] <= 1) printf("There is only 1 way to produce %d cents change.\n", n);else printf("There are %lld ways to produce %d cents change.\n", cnt[n], n); } return 0;}