[HNOI2001] 产品加工

题目描述

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

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

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

输入格式

第一行为一个整数 \(n\)。

接下来 \(n\) 行，每行三个非负整数 \(t_1,t_2,t_3\)，分别表示第 \(i\) 个任务在 A 机器上加工、B 机器上加工、两台机器共同加工所需要的时间。如果所给的时间 \(t_1\) 或 \(t_2\) 为 \(0\) 表示任务不能在该台机器上加工，如果 \(t_3\) 为 \(0\) 表示任务不能同时由两台机器加工。

输出格式

仅一行一个整数，表示完成所有 \(n\) 个任务的最少总时间。

关于本题:

也是头一次见这种状态定义方式比较特殊的，我们发现对于任务排序不太好做，考虑dp，那么状态的设计呢

Sol:

(1).f[i][t1][t2]:表示前i个任务，A用时t1，B用时t2是否可行
我们发现maxt大约在6000*5=30000，空间时间都不允许，考虑降维

(2).f[i][t1]:表示前i个任务，A用时t1，B的最小用时，这一步是把B的状态取消固定
但是此时发现空间为 6000*30000=180000000=1.8 * 10^8，MLE

(3).转移时发现f[i]之和f[i-1]有关，滚动一下就行了

滚动后记得数组赋初始值，然后你就要用memset每次对f[last]这一行赋值了对吗？你会TLE得理所应当。
原因是多次调用memset使程序效率降低,那我们干脆就用临时变量算了，由于再滚动了一维，所以maxt要倒序枚举

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=3e5+7;
int n,ans=0x3f3f3f3f,s;
int x,y,z,maxt;
int f[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x>>y>>z;
		maxt+=max(max(x,y),z);
		for(int j=maxt;j>=0;j--){
			int tmp=0x3f3f3f3f;
			if(x&&j>=x) tmp=min(tmp,f[j-x]);
			if(y) tmp=min(tmp,f[j]+y);
			if(z&&j>=z) tmp=min(tmp,f[j-z]+z);
			f[j]=tmp;
		}
	}
	for(int i=0;i<=maxt;++i)
		ans=min(ans,max(i,f[i]));
	cout<<ans<<'\n';
	return 0;
}

样例 #1

样例输入 #1

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

样例输出 #1

9

提示

对于所有数据，有 \(1\le n\le 6\times 10^3\)， \(0\le t_1,t_2,t_3\le 5\)。