HNOI 产品加工

给定你两台机器， 有$\large n $ 个物品需要你加工， 每个物品有三个时间 ，分别是在A，B机器上的用时以及A，B机器上共同的用时。

第一次遇见将答案带入DP状态的 的题目

用 表示处理了前$\large i $ 个物品 A机器用时为$\large j $时 B 机器最短的用时

答案为

)%0A#card=math&code=%5Chuge%20min%28max%28f%5Bn%5D%5Bi%5D%2Ci%29%29%0A)

我们考虑如何转移

%0A#card=math&code=%5CLarge%20f%5Bi%5D%5B%5Bj%5D%3Dmin%28f%5Bi%5D%5Bj%5D%2Bt_2%2Cf%5Bi-1%5D%5Bj-t_1%5D%2Cf%5Bi-1%5D%5Bj-z%5D%2Bz%29%0A)

分别代表扔给B机器 A机器自己搞 两台机器一起搞

无耻啊 这道题要卡常！

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
int n,t1[N],t2[N],t3[N],dp[2][N*5],w,ans=2e9;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&t1[i],&t2[i],&t3[i]);
        w+=max(t1[i],max(t2[i],t3[i]));
    }
    for(int i=1;i<=n;i++)
    {
        memset(dp[i%2],0x7f,sizeof(dp[i%2]));
        int inf=dp[i%2][0];
    //    w+=max(t1[i],max(t2[i],t3[i]));
        for(int j=w;j>=0&&dp[(i%2)^1][j]!=inf;j--)
        {
            if(j-t1[i]>=0&&t1[i]!=0)dp[i%2][j]=min(dp[i%2][j],dp[(i%2)^1][j-t1[i]]);
            if(t2[i]!=0)dp[i%2][j]=min(dp[i%2][j],dp[(i%2)^1][j]+t2[i]);
            if(j-t3[i]>=0&&t3[i]!=0)dp[i%2][j]=min(dp[i%2][j],dp[(i%2)^1][j-t3[i]]+t3[i]);
        }
    }
    for(int i=0;i<=w;i++)ans=min(ans,max(dp[n&1][i],i));
    printf("%d",ans);
    return 0;
}