uva 10306 - e-Coins

 1  /*
 2  Problem link
 3  Type: DP - Coins change
 4  Algorithm:
 5      First I use the function getP to search for a list of possible points with
 6       length = s from the origin and have possitive coordinates.
 7      Use the coins change algorithm (uva 166) with a few changes to find the
 8       minimum step to each point i got. Get the minimum for each point result.
 9  */
10  #include <iostream>
11  #include <cstdio>
12  #include <cstdlib>
13  #include <cstring>
14  #include <cmath>
15  #include <vector>
16  using namespace std;
17  
18  const int maxn = 50;
19  const int maxs = 310;
20  const int oo = 10000000;
21  const double eps = 1E-9;
22  
23  class Point
24  {
25  public:
26      int x,y;
27      Point() {}
28      Point(int xx, int yy): x(xx), y(yy) {}
29  };
30  
31  Point Points[maxn];
32  vector<Point> MyPoints;
33  int f[maxs][maxs][maxn];
34  int n,s;
35  
36  void readfile();
37  void getP();
38  int solve(Point& p);
39  
40  int main()
41  {
42      int ntest;
43      cin >> ntest;
44      for (int test=1; test<=ntest; test++)
45      {
46          int result = oo;
47          readfile();
48          getP();
49          for (unsigned int i=0; i<MyPoints.size(); i++)
50          {
51              int tmp = solve(MyPoints[i]);
52              result = result>tmp? tmp : result;
53          }
54          if (result!=oo) cout << result << endl;
55          else cout << "not possible" << endl;
56          MyPoints.clear();
57      }
58      return 0;
59  }
60  
61  void readfile()
62  {
63      cin >> n >> s;
64      for (int i=1; i<=n; i++)
65      {
66          cin >> Points[i].x >> Points[i].y;
67      }
68  }
69  
70  void getP()
71  {
72      for (int i=0; i<=s; i++)
73      {
74          double tmp = sqrt(s*s-i*i);
75          if (abs(int(tmp)-tmp)<=eps) MyPoints.push_back(Point(i,int(tmp)));
76      }
77  }
78  
79  int solve(Point& p)
80  {
81      for (int i=0; i<=p.x; i++)
82          for (int j=0; j<=p.y; j++)
83              for (int k=0; k<=n; k++) f[i][j][k] = oo;
84      for (int k=0; k<=n; k++) f[0][0][k] = 0;
85  
86      for (int i=0; i<=p.x; i++)
87          for (int j=0; j<=p.y; j++)
88              for (int k=1; k<=n; k++)
89                  if (Points[k].x<=i && Points[k].y<=j)
90                      f[i][j][k] = min(f[i-Points[k].x][j-Points[k].y][k]+1,f[i][j][k-1]);
91                  else f[i][j][k] = f[i][j][k-1];
92      return(f[p.x][p.y][n]);
93  }