Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Recommend
水题毕竟还是水题，只是告诫我们要学好英语，看懂题意，233
请你用一定面值的货币（每种面值不限单独数量），组成一定金额，问方案数。注意使用的货币总数不能超过100个。
还是生成函数，只是为了满足总数不超过100个的奇怪要求，新增一维记录当前已经使用了多少个货币并稍微改动转移即可。
1 #include <cstdio> 2 #include <cstring> 3 4 const int siz = 255; 5 const int lim = 250; 6 7 int n; 8 9 int f[105][siz]; 10 int t[105][siz]; 11 12 const int s[5] = 13 { 14 50, 15 25, 16 10, 17 5, 18 1 19 }; 20 21 signed main(void) 22 { 23 f[0][0] = 1; 24 25 for (int p = 0; p < 5; ++p) 26 { 27 int c = s[p]; 28 29 memset(t, 0, sizeof t); 30 31 for (int i = 0; i <= 100; ++i) 32 for (int j = 0; j <= lim; ++j)if (f[i][j]) 33 for (int k = 0; k * c <= lim; ++k) 34 if (i + k <= 100 && j + k * c <= lim) 35 t[i + k][j + k * c] += f[i][j]; 36 37 memcpy(f, t, sizeof f); 38 } 39 40 for (int i = 1; i <= 100; ++i) 41 for (int j = 0; j <= lim; ++j) 42 f[i][j] += f[i - 1][j]; 43 44 while (scanf("%d", &n) != EOF) 45 printf("%d\n", f[100][n]); 46 }
@Author: YouSiki
原文：http://www.cnblogs.com/yousiki/p/6424296.html