UVa - 11517 - Exact Change

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 103
9. using namespace std;
10. typedef long long LL;
11.  
12. int p, n, mn, ans;
13. int arr[S], dp[S][S*100];
14.  
15. int Exchange(int ind, int tot, int coin){
16.     if(tot >= p)return tot;
17.     if(ind >= n)return INT_MAX;
18.     if(dp[ind][tot] != -1)return dp[ind][tot];
19.     dp[ind][tot] = 0;
20.     dp[ind][tot] += Exchange(ind+1, tot+arr[ind], coin+1);
21.     mn = min(mn, dp[ind][tot]);
22.     Exchange(ind+1, tot, coin);
23.     return mn;
24. }
25.  
26. int Coins(int ind, int coin, int tot){
27.     if(tot == ans)return coin;
28.     if(tot > ans)return INT_MAX;
29.     if(ind >= n)return INT_MAX;
30.     if(dp[ind][tot] != -1)return dp[ind][tot];
31.     dp[ind][tot] = 0;
32.     dp[ind][tot] += Coins(ind+1, coin+1, tot+arr[ind]);
33.     mn = min(mn, dp[ind][tot]);
34.     Coins(ind+1, coin, tot);
35.     return mn;
36. }
37.  
38. void Do(){
39.     int t;
40.     sc(t);
41.     while(t--){
42.         sc(p);
43.         sc(n);
44.         memset(dp, -1, sizeof(dp));
45.         for(int i = 0; i < n; i++)sc(arr[i]);
46.         sort(arr, arr+n);
47.         reverse(arr, arr+n);
48.         mn = INT_MAX;
49.         ans = Exchange(0, 0, 0);
50.         cout << ans << " ";
51.         memset(dp, -1, sizeof(dp));
52.         mn = INT_MAX;
53.         cout << Coins(0, 0, 0) << endl;
54.     }
55. }
56.  
57. int main(){
58.     ios_base::sync_with_stdio(0); cin.tie(0);
59.     #ifndef ONLINE_JUDGE
60.     ///freopen("inp","r",stdout);
61.     ///freopen("contest.txt","w",stdout);
62.     #endif
63.     Do();
64.     return 0;
65. }