SHOW:
|
|
- or go back to the newest paste.
1 | #include <cstdio> | |
2 | #include <cstring> | |
3 | ||
4 | int m; | |
5 | - | int min; |
5 | + | |
6 | int coins[1000]; | |
7 | int sub(int s) | |
8 | - | int cur[100000]; |
8 | + | |
9 | - | int result[100000]; |
9 | + | |
10 | - | void sub(int s,int k) |
10 | + | return 2000000; |
11 | if (K[s] < 2000000) | |
12 | return K[s]; | |
13 | - | return; |
13 | + | |
14 | return 0; | |
15 | for (int i=0; i<n; ++i) | |
16 | - | if (min > k) |
16 | + | |
17 | - | { |
17 | + | int k = sub(s+coins[i]) + 1; |
18 | - | min = k; |
18 | + | if (k < K[s]) |
19 | - | memcpy(result, cur, k*sizeof(int)); |
19 | + | K[s] = k; |
20 | - | } |
20 | + | |
21 | - | return; |
21 | + | K[s] = 2000000 - 1; |
22 | } | |
23 | ||
24 | void main() | |
25 | - | cur[k] = coins[i]; |
25 | + | |
26 | - | sub(s+coins[i],k+1); |
26 | + | |
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 | } |