-
Notifications
You must be signed in to change notification settings - Fork 1
/
banknotes.cpp
44 lines (41 loc) · 1.05 KB
/
banknotes.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
#include <iostream>
#include <vector>
#define boost() cin.tie(0); cin.sync_with_stdio(0)
using namespace std;
int num, big, value, amount, counter, take;
int values[20001], quantity[20001], dp[20001], previous[20001];
int main()
{
boost();
cin >> num;
for (int i = 0; i < 20001; i += 1) {
previous[i] = 200000;
}
for (int i = 0; i < num; i += 1) {
cin >> values[i];
}
for (int i = 0; i < num; i += 1) {
cin >> quantity[i];
}
cin >> big;
previous[0] = 0;
for (int i = 0; i < num; i += 1) {
value = values[i];
amount = quantity[i];
for (int j = 1; j < 20001; j += 1) {
take = 2000000;
counter = 0;
for (int q = j; q >= 0; q -= value) {
if (counter > amount) {
break;
}
take = min(take, previous[q] + counter);
counter += 1;
}
dp[j] = take;
}
swap(dp, previous);
}
cout << previous[big] << endl;
return 0;
}