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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<bits/stdc++.h>
using namespace std;
const int MAXn = 10000;
const int MAXW = 1000;
const int INF = 0x3f3f3f3f;
int n, W;
int v_new[MAXn * 10 + 10];
int w_new[MAXn * 10 + 10];
bool is_limit[MAXn * 10 + 10];
int num_new;
int d[MAXW + 10];
inline int read() {
register char c;
for (c = getchar(); (c < '0' || c>'9') && c != '-'; c = getchar());
register bool f = c == '-';
register int s = f ? 0 : c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar())s = (s << 3) + (s << 1) + c - '0';
return f ? -s : s;
}
void bin_divide(int v, int w, int num, int v_new[], int w_new[], int& num_new, bool is_limit[]) {
for (int i = 1; num >= i; i <<= 1) {
v_new[++num_new] = v * i;
w_new[num_new] = w * i;
is_limit[num_new] = 1;
num -= i;
}
if (num > 0) {
v_new[++num_new] = v * num;
w_new[num_new] = w * num;
is_limit[num_new] = 1;
}
}
void put_in() {
W = read();
n = read();
int v, w, num;
for (int i = 1; i <= n; i++) {
w = read();
v = read();
num = read();
if (num) bin_divide(v, w, num, v_new, w_new, num_new, is_limit);
else {
v_new[++num_new] = v;
w_new[num_new] = w;
is_limit[num_new] = 0;
}
}
}
void rec(int v[], int w[], bool is_limit[], int W, int num) {
for (int i = 1; i <= num; i++) {
if (is_limit[i]) {
for (int j = W; j >= w[i]; j--) d[j] = max(d[j], d[j - w[i]] + v[i]);
} else {
for (int j = w[i]; j <= W; j++) d[j] = max(d[j], d[j - w[i]] + v[i]);
}
}
}
int eva_maxV(int W) {
int ans = -INF;
for (int i = 0; i <= W; i++) ans = max(ans, d[i]);
return ans;
}
int main() {
put_in();
rec(v_new, w_new, is_limit, W, num_new);
cout << eva_maxV(W);
}
|
