Bzoj 1222(DP)

BZOJ 1222
设$f(i)$为A在$i$时时B在$f(i)$时,并且$f(i)$最小
那么分3种情况转移:
1、第$i$个物品放A
2、第$i$个物品放B
3、第$i$个物品放AB

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int INF = 10000000, MAXN = 6000 + 5, MAXM = 30000 + 5;
int n, m, a[MAXN], b[MAXN], c[MAXN], f[MAXM];
void clean() {}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
if (!a[i]) a[i] = INF;if (!b[i]) b[i] = INF;if (!c[i]) c[i] = INF;
m += min(min(a[i], b[i]), c[i]);//直接顺序加工
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
int t = INF;
if (j - a[i] >= 0) t = min(t, f[j - a[i]]);
t = min(t, f[j] + b[i]);
if (j - c[i] >= 0) t = min(t, f[j - c[i]] + c[i]);
f[j] = t;
}
}
int ans = INF;
for (int i = 1; i <= m; i++) ans = min(ans, max(i, f[i]));
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------