洛谷P2224 [HNOI2001]产品加工 题解

题目链接：P2224 [HNOI2001]产品加工

题意：

某加工厂有 A、B 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。

某一天，加工厂接到 $n$ 个产品加工的任务，每个任务的工作量不尽一样。

你的任务就是：已知每个任务在 A 机器上加工所需的时间 $t_1$，B 机器上加工所需的时间 $t_2$ 及由两台机器共同加工所需的时间 $t_3$，请你合理安排任务的调度顺序，使完成所有 $n$ 个任务的总时间最少。

显然dp

设 $dp[i][j]$ 表示只考虑前 $i$ 个物品，第一台机器花了 $j$ 时间，第二台机器花的最少时间

不难发现

$$dp[i][j]=\min(dp[i-1][j]+b[i],dp[i-1][j-a[i]],dp[i-1][j-c[i]]+c[i])$$

然后滚动数组一下就好了

注意这题卡常很恶心（恼

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(3e4+65)

int n,a[N],b[N],c[N],dp[2][N],sum,cur,pre,mn;
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a>b?a:b;}
signed main()
{
    read(n);
    memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        read(a[i]),read(b[i]),read(c[i]);
        sum+=max(a[i],max(b[i],c[i]));
        cur=i&1,pre=cur^1;
        memset(dp[cur],0x3f,(sum+1)*sizeof(int));
        for(int j=0; j<=sum; j++)
        {
            if(b[i])dp[cur][j]=min(dp[cur][j],dp[pre][j]+b[i]);
            if(j>=a[i]&&a[i])dp[cur][j]=min(dp[cur][j],dp[pre][j-a[i]]);
            if(j>=c[i]&&c[i])dp[cur][j]=min(dp[cur][j],dp[pre][j-c[i]]+c[i]);
        }
    }
    mn=INF;
    for(int i=0; i<=sum; i++)
        mn=min(mn,max(dp[n&1][i],i));
    write(mn);
    return 0;
}