题目戳我
看到这个题第一眼：哇塞状态好多怎么维护鸭
第二眼：咦，我们可以用\(f[i][j]\)代表加工到第\(i\)个产品、第一个机器用了\(j\)时间时第二个机器用的时间
这样就可以维护所有状态辣~！
解决了我是谁的问题，接下来该考虑我从哪里来了
转移可以考虑三种情况：
1.选\(t1,f[i][j]=\min\{f[i-1][j],f[i-1][j-t1]\},t1\neq 0\&\&t1\leq j\)
2.选\(t2,f[i][j]+=t2,t2\neq 0\)
3.选\(t3,f[i][j]=\min\{f[i-1][j],f[i-1][j-t3]+t3\},t3\neq 0\&\&t3\leq j\)
最后统计答案的时候枚举第一个机器的时间，则\(ans=\min\{\max\{i,f[n][i]\}\},i\in [0,\sum \max\{t1,t2,t3\}]\)
枚举的上界定为\(\sum \max\{t1,t2,t3\}\)而不是\(\min\)是因为防止毒瘤出题人令\(t3>t1,t2\)
这时，你又回去看了这个题第三眼，发现了问题：
数据范围太大啦！！！
没事滚滚就好了把第一维滚掉，Accepted！
Main Code：
#define N 6010
int n,f[N*5],ans=INF,maxt;
int main(){
Read(n);
memset(f,0x3f,sizeof(f));
f[0]=0;
for(rg int i=1;i<=n;i++){
int t1,t2,t3;
Read(t1),Read(t2),Read(t3);
maxt+=max(max(t1,t2),t3);
for(rg int j=maxt;j>=0;j--){
if(t2)f[j]+=t2;
else f[j]=INF;
if(t1&&j>=t1)f[j]=min(f[j],f[j-t1]);
if(t3&&j>=t3)f[j]=min(f[j],f[j-t3]+t3);
}
}
for(rg int i=0;i<=maxt;i++){
ans=min(ans,max(i,f[i]));
}
cout<<ans<<endl;
return 0;
}
完结撒fa♂
原文：https://www.cnblogs.com/juruoajh/p/12644173.html