﻿ [HNOI 2001]产品加工

5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1

9

## 题解

\$\$f[i]=Min(f[i],f[i-t_1],f[i-t_3]+t_3)\$\$

\$\$ans=Min(ans,Max(i,f[i]))\$\$

``` 1 #include<set>
2 #include<map>
3 #include<cmath>
4 #include<ctime>
5 #include<queue>
6 #include<stack>
7 #include<cstdio>
8 #include<string>
9 #include<vector>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 using namespace std;
15 const int N=6000;
16 const int INF=1e9;
17
18 int Min(const int &a,const int &b) {return a<b ? a:b;}
19 int Max(const int &a,const int &b) {return a>b ? a:b;}
20 int n,m,ans;
21 int t1,t2,t3;
22 int f[N*5+5];
23
24 int main()
25 {
26     scanf("%d",&n);
27     memset(f,127,sizeof(f));
28     f[0]=0;
29     while (n--)
30     {
31         scanf("%d%d%d",&t1,&t2,&t3);
32         t1=!t1 ? INF :t1;
33         t2=!t2 ? INF :t2;
34         t3=!t3 ? INF :t3;
35         m+=Min(t1,Min(t2,t3));
36         for (int i=m;i>=0;i--)
37         {
38             if (f[i]<INF) f[i]+=t2;
39             if (i>=t1) f[i]=Min(f[i],f[i-t1]);
40             if (i>=t3) f[i]=Min(f[i],f[i-t3]+t3);
41         }
42     }
43     ans=INF;
44     for (int i=0;i<=m;i++) ans=Min(ans,Max(i,f[i]));
45     printf("%d
",ans);
46     return 0;
47 }```