ACM: 147 - Dollars

也是一直想學的DP換零錢問題，很有趣。

NOTE

注意浮點數誤差的問題

REFERENCE

Coin Change

CODE

#include <iostream>

enum { MAX = 300 * 100 / 5, COINS = 11 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; //value*100/5

    long long r[MAX+1];

    int i, j;

    for(i=0; i<=MAX; ++i)

        r[i] = 1;

    for(i=1; i<COINS; ++i)

        for(j=coin[i]; j<=MAX; ++j)

            r[j] = r[j-coin[i]] + r[j];

    while( (scanf("%d.%d", &i, &j) != EOF) && (i+j != 0) )

        printf("%3d.%02d%17lld\n", i, j, r[(i*100+j)/5]);

    return 0;

}