注意时间都是 <= 5的。。
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<algorithm>
5 #include<iostream>
6
7 using namespace std;
8
9 template<typename Q> Q read(Q& x) {
10 static char c, f;
11 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
12 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
13 if(f) x = -x;
14 return x;
15 }
16 template<typename Q> Q read() {
17 static Q x; read(x); return x;
18 }
19
20 const int N = 6000 + 10, INF = 6000 * 5 + 10;
21 int a[N], b[N], c[N];
22 int f[N * 5];
23
24 int main() {
25 #ifdef DEBUG
26 freopen("in.txt", "r", stdin);
27 freopen("out.txt", "w", stdout);
28 #endif
29
30 int n, maxw = 0;
31 scanf("%d", &n);
32 for(int i = 1; i <= n; i++) {
33 scanf("%d%d%d", a + i, b + i, c + i);
34 if(!a[i]) a[i] = INF;
35 if(!b[i]) b[i] = INF;
36 if(!c[i]) c[i] = INF;
37 maxw += min(min(a[i], b[i]), c[i]);
38 }
39 memset(f, 0x3f, sizeof f);
40 f[0] = 0;
41 for(int i = 1; i <= n; i++) {
42 for(int j = maxw; j >= 0; j--) {
43 f[j] += b[i];
44 if(j >= a[i]) f[j] = min(f[j], f[j - a[i]]);
45 if(j >= c[i]) f[j] = min(f[j], f[j - c[i]] + c[i]);
46 }
47 }
48 int ans = INF;
49 for(int i = 0; i <= maxw; i++) ans = min(ans, max(i, f[i]));
50 printf("%d
", ans);
51
52 return 0;
53 }