一、问题

题目描述

某加工厂有 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$ 个任务的最少总时间。

样例 #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$。

二、分析

1、状态表示

$f[i][j][k]$表示，分配前$i$个任务，A机器上花费的时间是$j$，B机器上花费的时间是$k$，我们的$f$数组是一个$bool$数组，即判断这种方案是否存在。

那么我们求最终的答案呢？当我们求出所有状态后，只需要贪心地从小到大枚举判断当前方案是否存在即可。

但是这种三维DP明显超时了，空间也超了。所以，我们需要对这种定义方式进行优化。

$f[i][j]$表示分配前$i$个任务，机器$A$上的时间是$j$，$f$数组存储的是在$A$分配$j$时间的条件下，我们的$B$机器分配的最短时间。最后贪心枚举判断一下即可。

这里告诉我们的经验就是：当题目中有多个限制条件的时候，我们可以考虑将其中一个限制转化为状态中的一个维度。

2、状态转移

这里的状态转移采用了背包问题的思想。
我们针对第$i$个物品的分配方式进行讨论。
在题目允许的情况下， 要么分配给$A$，要么分配给$B$，要么分配给$A+B$。
$$\begin{gathered} f[i][j]=min(f[i][j],f[i-1][j-t_a]) \\ f[i][j]=min(f[i][j],f[i-1][j]+t_b) \\ f[i][j]=min(f[i][j],f[i-1][j-t_{ab}]+t_{ab}) \end{gathered}$$

3、空间优化

因为我们只用到了第$i-1$层的信息，所以我们需要用滚动数组。因为我们求的是最小值，当我们滚到某一层时，需要先将这一层初始化为$INF$。避免之前遗留的状态影响到当前的转移。

在洛谷提交需要开$O2$。

三、代码

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 6e3 + 10;
int a[N], b[N], c[N];
int n;
int f[3][N * 5];
void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ )
		cin >> a[i] >> b[i] >> c[i];

	memset(f, INF, sizeof f);
	f[0][0] = 0;
	for(int i = 1; i <= n; i ++ )
	{
		memset(f[i & 1], INF, sizeof f[i & 1]);
		for(int j = 0; j <= 5 * n; j ++ )
		{
			if(a[i] && j >= a[i])
				f[i & 1][j] = min(f[(i - 1) & 1][j - a[i]], f[i & 1][j]);
			if(b[i])
				f[i & 1][j] = min(f[(i - 1) & 1][j] + b[i], f[i & 1][j]);
			if(c[i] && j >= c[i])
				f[i & 1][j] = min(f[(i - 1) & 1][j - c[i]] + c[i], f[i & 1][j]);
		}	
	}


	int minv = INF;
	for(int i = 0; i <= 5 * n; i ++ )
		minv = min(minv,max(i, f[n & 1][i]));

	cout << minv << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
}