uva 11517 - Exact Change

/*
Problem link
Type: DP - Coin change
Algorithm:
*/



 1  #include <iostream>
 2  #include <cmath>
 3  #include <cstdio>
 4  #include <cstdlib>
 5  using namespace std;
 6  
 7  const int maxn = 10010*5;
 8  const int maxs = 110;
 9  const long long oo = 2000000000;
10  
11  long long f[maxn][maxs];
12  int a[maxs];
13  int n,s;
14  
15  void readfile();
16  int solve(long long& value);
17  
18  int main()
19  {
20      int result, ntest;
21      long long value;
22  
23      cin >> ntest;
24      for (int i=1; i<=ntest; i++)
25      {
26          readfile();
27          result = solve(value);
28          cout << result << " " << value << endl;
29      }
30  
31      return 0;
32  }
33  
34  void readfile()
35  {
36      cin >> n >> s;
37      for (int i=1; i<=s; i++) cin >> a[i];
38  }
39  
40  int solve(long long& value)
41  {
42      for (int i=0; i<=n*5; i++)
43          for (int j=0; j<=s; j++) f[i][j] = +oo;
44  
45      for (int j=0; j<=s; j++) f[0][j] = 0;
46  
47      for (int i=1; i<=n*5; i++)
48          for (int j=1; j<=s; j++)
49              if (a[j]<=i) f[i][j] = min(f[i-a[j]][j-1]+1,f[i][j-1]);
50              else f[i][j] = f[i][j-1];
51  
52      for (int i=n; i<=n*5; i++)
53          if (f[i][s]!=+oo)
54          {
55              value = f[i][s];
56              return(i);
57          }
58      return 0;
59  }