HDU 2069 Coin Change
http://acm.hdu.edu.cn/showproblem.php?pid=2069
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int a[1111][1111]; int b[6]= {1, 5, 10, 25, 50}; int main() { int n; while(~scanf("%d", &n)) { memset(a, 0, sizeof(a)); a[0][0]=1; for(int j = 0; j <= 4; j ++) { for(int i = b[j]; i <= n; i ++) { for(int k = 1;k <= 100; k++) { if(i >= b[j]) a[k][i] += a[k-1][i - b[j]]; } } } int sum = 0; for(int i = 0; i <= 100; i ++) { sum += a[i][n]; } printf("%d\n",sum); } return 0; }
优质内容筛选与推荐>>