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

  題目大意：有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;  
}