UVa 147 Dollars：经典DP&硬币组合数&整数拆分

UVa 147 Dollars：经典DP&硬币组合数&整数拆分2014-07-29

147 - Dollars

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

和UVa 357一样。

注意所有数除以5再算。

完整代码：

/*0.019s*/#include<cstdio>#include<cstring>const int coin[11] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};const int maxn = 6001;long long dp[maxn];int main（）{int i, k, n, a, b;dp[0] = 1;for （k = 0; k < 11; ++k）for （i = coin[k]; i < maxn; ++i）///注意状态转移进行的顺序dp[i] += dp[i - coin[k]];while （scanf（"%d.%d", &a, &b）,a||b）{n = （100 * a + b） / 5;printf（"%3d.%02d%17lld
", a, b, dp[n]）;}return 0;}