钱币问题
作者:
MuQY
,
2024-03-26 23:46:42
,
所有人可见
,
阅读 5
#include <bits/stdc++.h>
using namespace std;
int money[11] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
long long dp[15][30005]; // dp[i][j]表示用前i种钱币正好凑j元钱的方案数
int main()
{
double x;
for (int i = 0; i <= 11; i++)
dp[i][0] = 1; // 什么也不选也是一种方案
while (cin >> x)
{
if (x == 0)
break;
int coin = (x * 100 + 0.5); // 精度问题,我也是醉了。。。
for (int i = 1; i <= 11; i++)
for (int j = 1; j <= coin; j++)
{
dp[i][j] = dp[i - 1][j]; // 不选第i种
if (j >= money[i - 1])
dp[i][j] += dp[i][j - money[i - 1]];
}
printf("%6.2lf%17lld\n", x, dp[11][coin]);
}
return 0;
}