【题解】[HNOI2001]产品加工

2022-06-29 OI 动态规划

题目描述

某加工厂有 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

样例输出 #1

提示

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

题解

如果知道最终 $A$ 机器加工完所有产品的时间为 $a$ ， $B$ 的时间为 $b$ ，则答案是 $\min{\max{a,b}}$ 。但是普通的DP不能一下求出两个时间，所以我们要将一个时间写入状态。

设 $f_{i,j}$ 表示前 $i$ 个物品中， $A$ 加工的时间为 $j$ 时， $B$ 所需的最小时间。则：

f_{i,j} = \min{f_{i-1,j-t1_i}, f_{i-1,j}+t2_i,f_{i-1,j-t3_i}+t3_i}

答案为 $\min{\max{j,f_{i,j}}}$ 。注意枚举 $j$ 时，上界为 $1~i$ 中 $\max{t1_i,t2_i,t3_i}$ 的和。

代码

#include <cstdio>
#define MAXN 6000
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
int n, t1[MAXN + 3], t2[MAXN + 3], t3[MAXN + 3], f[2][MAXN * 5 + 3], s, ans = 1 << 30;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &t1[i], &t2[i], &t3[i]);
    for (int i = 1; i <= n; i++) {
        s += max(max(t1[i], t2[i]), t3[i]);
        for (int j = 0; j <= s; j++) {
            f[i & 1][j] = 1 << 30;
            if (t2[i])
                f[i & 1][j] = f[i - 1 & 1][j] + t2[i];
            if (j >= t1[i] && t1[i])
                f[i & 1][j] = min(f[i & 1][j], f[i - 1 & 1][j - t1[i]]);
            if (j >= t3[i] && t3[i])
                f[i & 1][j] = min(f[i & 1][j], f[i - 1 & 1][j - t3[i]] + t3[i]);
        }
    }
    for (int j = 0; j <= s; j++)
        ans = min(ans, max(j, f[n & 1][j]));
    printf("%d\n", ans);
    return 0;
}

总结

遇到这类需要求一个以上最优值的时候，可以把这些值写入状态。