uva 147 - Dollars

 1 /*
 2  Problem link
 3  Type: DP
 4  Algorithm:
 5      Define a const array of currency.
 6      Let f(i,j) be the number of ways to change i into sum of currency[1..j].
 7      For each value of i from 0 to n, if currency[j]<=i, then i can be exchange
 8       into currency[j]. If we decide to choose currency[j] to our way then
 9       the number of ways is f[i-currency[j],j] else then it is f[i,j-1];
10      Hence we have the formula:
11          f(i,j) = f(i-currency[j],j)+f(i,j-1) if currency[j]<=i;
12          else f(i,j) = f(i,j-1);
13  */
14  #include <iostream>
15  #include <cstdio>
16  #include <cstring>
17  #include <cstdlib>
18  #include <iomanip>
19  using namespace std;
20  
21  const int maxn = 30010;
22  const int currency[12] = {0,5,10,20,50,100,200,500,1000,2000,5000,10000};
23  const double eps = 10E-9;
24  
25  double n;
26  long long f[maxn][15];
27  
28  int main()
29  {
30      memset(f,0,sizeof(f));
31      for (int i=0; i<=11; i++) f[0][i] = 1;
32      for (int i=0; i<=maxn; i++)
33          for (int j=1; j<=11; j++)
34              if (currency[j]<=i) f[i][j] = f[i-currency[j]][j] + f[i][j-1];
35              else f[i][j] = f[i][j-1];
36      while (true)
37      {
38          cin >> n;
39          if (n==0) break;
40          int tmp = (n+eps)*100;
41          cout.setf(ios::showpoint);
42          cout.setf(ios::fixed,ios::floatfield);
43          cout << setw(6) << setprecision(2) << n << setw(17) << f[tmp][11] << endl;
44      }
45      return 0;
46  }