-
Notifications
You must be signed in to change notification settings - Fork 0
/
debug.cpp
48 lines (40 loc) · 862 Bytes
/
debug.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
pair<int, int> coin[40];
int dp[40][10010];
int coinChange(int i, int k){
if(k==0) return 0;
if(i<0||k<0) return 100000000;
if(dp[i][k]!=-1) return dp[i][k];
int r1=coinChange(i, k-coin[i].first)+1;
int r2=coinChange(i-1, k);
dp[i][k] =min(r1, r2);
return dp[i][k];
}
void traceBack(int i, int k, int res){
if(i<0|| res==0) return;
if(dp[i][k-coin[i].first]==res-1){
coin[i].second++;
traceBack(i, k-coin[i].first, res-1);
}
else {
traceBack(i-1, k, res);
}
}
int main(){
memset(dp, -1, sizeof(dp));
int n, k; cin>>n>>k;
for(int i=0; i<n; i++){
cin>>coin[i].first;
coin[i].second=0;
}
int res = coinChange(n-1, k);
cout<<res<<endl;
traceBack(n-1, k, res);
for(int i=0; i<n; i++){
if(coin[i].second>0){
cout<<coin[i].first<<" "<<coin[i].second<<endl;
}
}
return 0;
}