bzoj 1222: [HNOI2001]产品加工

.

题意：有两台机器，给出n个产品在1号机器、2号机器、两台机器一起的加工时间，0表示不能以某种方式加工，问最快加工时间。
题解：DP
很强。$f[i][j]$表示前i个产品，在2号机器上用了j的时间，1号机器用的时间。第一维滚一下。转移看代码。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,t[6010][3],f[30010];
const int inf=0x3f3f3f3f;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&t[i][0],&t[i][1],&t[i][2]);
        for(int j=0;j<3;j++)
        if(!t[i][j])
        t[i][j]=inf;
    }
    int maxt=5*n;
    memset(f,63,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=maxt;j>=0;j--)
        {
            int hh=inf;
            hh=min(hh,f[j]+t[i][0]);
            if(j>=t[i][1])
            hh=min(hh,f[j-t[i][1]]);
            if(j>=t[i][2])
            hh=min(hh,f[j-t[i][2]]+t[i][2]);
            f[j]=hh;
        }
    }
    int ans=inf;
    for(int i=0;i<=maxt;i++)
    ans=min(ans,max(i,f[i]));
    printf("%d",ans);
}