Advertisement
r57shell

Untitled

Dec 19th, 2013
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. int m;
  5. int n;
  6. int coins[1000];
  7. int sub(int s)
  8. {
  9.  if (s > m)
  10.     return 2000000;
  11.  if (K[s] < 2000000)
  12.     return K[s];
  13.  if (s == m)
  14.     return 0;
  15.  for (int i=0; i<n; ++i)
  16.  {
  17.      int k = sub(s+coins[i]) + 1;
  18.      if (k < K[s])
  19.          K[s] = k;
  20.  }
  21.  K[s] = 2000000 - 1;
  22. }
  23.  
  24. void main()
  25. {
  26.  scanf("%d %d",&n, &m);
  27.  for (int i=0; i<n; ++i)
  28.    scanf("%d", coins[i]);
  29.  for (int i=0; i<m; ++i)
  30.    K[i] = 2000000;
  31.  sub(0,0);
  32.  printf("Count: %d",K[0]);
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement