题目大意：也是硬币兑换问题，与147、674用同样的方法即可解决。
1 #include <cstdio> 2 #include <cstring> 3 #define MAXN 30001 4 5 const int coin[5] = {1, 5, 10, 25, 50}; 6 long long dp[MAXN]; 7 8 int main() 9 { 10 #ifdef LOCALi 11 freopen("in", "r", stdin); 12 #endif 13 memset(dp, 0, sizeof(dp)); 14 dp[0] = 1; 15 for (int k = 0; k < 5; k++) 16 for (int i = 1; i < MAXN; i++) 17 if (i >= coin[k]) 18 dp[i] += dp[i-coin[k]]; 19 int n; 20 while (scanf("%d", &n) != EOF) 21 { 22 if (dp[n] == 1) printf("There is only 1 way to produce %d cents change. ", n); 23 else printf("There are %lld ways to produce %d cents change. ", dp[n], n); 24 } 25 return 0; 26 }