完全背包,注意精度问题,我是直接把小数分成两个整数做的。
代码如下:
#include <iostream> #include <cstdio> using namespace std; long long dp[8005]; int coin[11] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; int main() { int num, a, b; dp[0] = 1; for(int i=0; i<11; ++i) { for(int j=0; j<6001; ++j) dp[j + coin[i]] += dp[j]; } while(scanf("%d.%d", &a, &b) != EOF) { num = (a * 100 + b) / 5; if(num == 0) break; if(b >= 10) printf("%3d.%d", a, b); else printf("%3d.0%d", a, b); printf("%17lld\n", dp[num]); } return 0; }