uva 10313 - Pay the Price

 1 /*
 2  Problem link
 3  Type: DP - coin change
 4  Algorithm:
 5      Let f(i,j,k) be the number of ways to make up i using the
 6      values from 1..j so that the number of coins does not exceed k.
 7  
 8      If choose j: f(i-j,j,k-1);
 9      else f(i,j-1,k);
10  
11      One trick of this problem is that the number of coins never
12      exceed 300 then ifk>300 then k = 300.
13  
14      Run time: O(n^3).
15  */
16  #include <iostream>
17  #include <cstdio>
18  #include <sstream>
19  #include <cmath>
20  using namespace std;
21  
22  const int maxn = 310;
23  
24  long long f[maxn][maxn][maxn];
25  int a[3];
26  
27  void Calculate();
28  
29  int main()
30  {
31      Calculate();
32      string line;
33      int i;
34      while (!cin.eof())
35      {
36          getline(cin,line);
37          if (line == "") break;
38  
39          a[1] = -1; a[2] = -1;
40          i = 0; a[i] = 0;
41          for (unsigned int j=0; j<line.length(); j++)
42          {
43              if (line[j]==' ') a[++i] = 0;
44              else a[i] = a[i]*10 + int(line[j]) - 48;
45          }
46  
47          if (a[1]>300) a[1] = 300;
48          if (a[2]>300) a[2] = 300;
49          if (a[1]!=-1 && a[2]!=-1) cout << f[a[0]][a[0]][a[2]] - f[a[0]][a[0]][a[1]-1] << endl;
50          else if (a[1]!=-1) cout << f[a[0]][a[0]][a[1]] << endl;
51          else cout << f[a[0]][a[0]][a[0]] << endl;
52      }
53      return 0;
54  }
55  
56  void Calculate()
57  {
58      for (int j=0; j<maxn; j++)
59          for (int k=0; k<=300; k++)
60              f[0][j][k] = 1;
61  
62      for (int i=1; i<=300; i++)
63          for (int j=1; j<=300; j++)
64              for (int k=1; k<=300; k++)
65                  if (j<=i) f[i][j][k] = f[i-j][j][k-1]+f[i][j-1][k];
66                  else f[i][j][k] = f[i][j-1][k];
67  }