[bzoj1222]产品加工

用f[i][j]表示完成前i个任务，在A机器上加工j小时时B机器上最少要工作多小时，转移就分为三种，即$f[i][j]=min(f[i-1][j-t1],f[i-1][j]+t2,f[i-t3]+t3)$，然后这个东西可以用类似于背包的方式优化到1维（注意要从大到小枚举）

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,s,ans,f[30005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a,&b,&c);
        if (!a)a=1e5;
        if (!b)b=1e5;
        if (!c)c=1e5;
        for(int j=5*n;j>=0;j--){
            f[j]+=b;
            if (j>=a)f[j]=min(f[j],f[j-a]);
            if (j>=c)f[j]=min(f[j],f[j-c]+c);
        }
    }
    ans=f[0];
    for(int i=1;i<=5*n;i++)ans=min(ans,max(i,f[i]));
    printf("%d",ans);
}