题解 [HNOI2001]产品加工

题目描述

某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。
你的任务就是：已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请你合理安排任务的调度顺序，使完成所有n个任务的总时间最少。

输入输出格式

输入格式
（输入文件共n+1行）
第1行为 n。 n是任务总数（1≤n≤6000）
第i+1行为3个[0，5]之间的非负整数t1,t2,t3，分别表示第i个任务在A机器上加工、B机器上加工、两台机器共同加工所需要的时间。如果所给的时间t1或t2为0表示任务不能在该台机器上加工，如果t3为0表示任务不能同时由两台机器加工。

输出格式
最少完成时间

输入输出样例

输入样例#1

5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1

输出样例#1

9

解题思路

终于有一道状态转移方程面积不那么庞大的DP题了（手动滑稽_ hua|ji_）
很显然，如果我们分别考虑某个任务由第一个机器或者由第二个机器来完成的话，不管是时间复杂度还是空间复杂度都输无法承受的，那么我们来考虑压维
我们定义状态变量 f [ i ] 表示第一个机器工作了 i 分钟时第二个机器的工作时间，外层循环就是从 1 到 n ，也就是循环任务数量，当我们每枚举到一个任务时，先考虑它是否能够被安排给第二个机器，如果可以，我们就把 f [ i ] 加上当前的 t2 ，如果不行，就还把他设为一个极大值；然后我们再来考虑把它分给两个机器或是两个机器共同完成的最优解，如果可以被分配给第一个机器时，第二个机器的时间就不用增加，转移方程即为：

f [ i ] = min ( f [ i ] , f [ i - t1 ] ) ;

如果他能被分配给两个机器共同完成时，不仅第一个机器的时间要转移，第二个机器的时间也要增加，故转移方程为：

f [ i ] = min ( f [ i ] , f [ i - t3 ] + t3 ) ;

需要注意的细节是，每次进行转移的时候内层循环应循环完成任务的总时间，又因为我们压掉了循环物品的那一维，所以内层循环应从总时间循环到零，在这里我们可以进行一个优化，就是在读入的时候边读边进行状态转移，定义一个 sum 变量每次加上读入的 t1 , t2 , t3 中的最大值，循环结束时的 sum 即为完成任务的总时间
然后是最终答案，我们定义一个 ans ，初始化成极大值，然后循环总时间，每次取 min ( ans , max ( i , f [ i ] ) ) 即为最终答案
至于为什么是 max ( i , f [ i ] ) ，因为 i 表示第一个机器的时间，f [ i ]为第二个机器的时间，如果你只取较小的那个时间，则另一个机器很显然还没有完成任务，就不是满足条件的答案，只有你取了两个时间中的最大值才能保证两个机器都完成了任务
下面是C++代码，具体细节看注释

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rr register
using namespace std;

const int maxn=3e4+10;
const int inf=2147482647;
int n,t1,t2,t3,sum=0,ans=inf;
int f[maxn];

inline int read(){//珂朵莉版快读~~~
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
    return chtholly*willem;
}

int main(){
    memset(f,127/3,sizeof(f));
    f[0]=0;//初始化f
    n=read();for(rr int i=1;i<=n;i++){
        t1=read(),t2=read(),t3=read();
        sum+=max(t1,max(t2,t3));
        for(rr int j=sum;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(rr int i=0;i<=sum;i++)ans=min(ans,max(i,f[i]));
    printf("%d\n",ans);
    return 0;
}