Description

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

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

n <= 6000, t_1,t_2,t_3\in[0,5],0表示不行

Solution

这种奇葩的 dp 是第一次见。如果状态以时间为维度定义的话会炸掉,所以考虑这样定义状态:f_{i,j} 表示完成了前 i 项任务,A 机子花了 j 时间,B 机子花的最小时间。

为什么这样定义状态是对的呢?直接考虑把两个机子一起做的放到最前面做就可以了,就无需考虑顺序问题了。详情见 wjyyy大佬的博客

转移方程可以很轻松的写出来,但是需要优化。考虑枚举上下界,即计算出 f_{i,j} 有取值的 j 的上下界。最后答案跑 min 即可

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
    int ret = 0; int rev = 0;
    char c = getchar();
    while (!isdigit(c))
        rev |= (c == '-'), c = getchar();
    while (isdigit(c))
        ret = 10 * ret + c - '0', c = getchar();
    return rev ? -ret : ret;
}

inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}

const int maxn = 6000 + 5;

int f[maxn * 5];

int main()
{
    int n = read(), up, down, tmp, ans = 0x7fffffff;
    FOR(i, 1, n)
    {
        int a = read(), b = read(), c = read();
        up += max(max(a, b), c), tmp = down;
        down = 0x7fffffff;
        DEC(j, up, tmp)
        {
            int t = 0x3fffffff;
            if (a && j - a >= tmp) t = min(t, f[j - a]);
            if (b) t = min(t, f[j] + b);
            if (c && j - c >= tmp) t = min(t, f[j - c] + c);
            if (t < 0x3fffffff)
                down = min(down, j);
            f[j] = t;
        }
    }
    FOR(i, down, up)
        ans = min(ans, max(i, f[i]));
    printf("%d\n", ans);
    return 0;
}
最后修改日期:2021年1月31日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。