解题报告：P2365 任务安排

发表于 分类于

题意

洛谷：link

nn 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 nn 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 ii 个任务单独完成所需的时间为 tit_i。在每批任务开始前，机器需要启动时间 ss，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 fif_i。请确定一个分组方案，使得总费用最小。

数据范围：对于 100%100\% 的数据，1≤n≤50001\le n \le 5000，0≤s≤500 \le s \le 50，1≤ti,fi≤1001\le t_i,f_i \le 100。

思路

首先考虑暴力 dp

设当前状态为 dpi,jdp_{i, j}，表示在前 ii 个任务中分出 jj 组完成所需要的最小时间

则显然有如下转移：

dpi,j=min⁡1≤k≤i{dpk−1,j−1+∑k≤p≤ifp×(j×s+∑1≤p≤itp)}dp_{i, j} = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1, j - 1} + \sum \limits_{k \le p \le i} f_p \times \left(j \times s + \sum \limits_{1 \le p \le i} t_p\right) \right\rbrace

使用前缀和即可解决，时间复杂度为 O(n3)O(n ^ 3)

考虑优化，由于题目中没有规定分组个数，尝试将 jj 的维度优化掉

那么定义新的含意下 dpidp_i 表示前 ii 个任务分出若干组所需要的最小时间

现在我们发现这对原来转移会造成影响：我们无法再计算出 j×sj \times s，也就无法正常转移

此时我们使用费用提前计算的思想，考虑我们每添加一组，那么当前组的第一个一直到最后一个元素的结束时间都会因此推迟 ss，那么就会造成 s×∑fjs \times \sum f_j 的费用，我们提前将这个费用累加至 dpidp_i 即可

那么也就得出了新的状态转移方程

dpi=min⁡1≤k≤i{dpk−1+∑k≤p≤ifp×∑1≤p≤itp+∑k≤p≤nfp×s}dp_{i} = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1} + \sum \limits_{k \le p \le i} f_p \times \sum \limits_{1 \le p \le i} t_p + \sum \limits_{k \le p \le n} f_p \times s \right\rbrace

时间复杂度为 O(n2)O(n ^ 2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 1e5 + 5;
    int n, s;
    LL t[MAXN], c[MAXN];
    LL sumt[MAXN], sumc[MAXN];
    LL dp[MAXN];
    int main()
    {
        std::memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        scanf("%d%d", &n, &s);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld", &t[i], &c[i]);
            sumt[i] = sumt[i - 1] + t[i], sumc[i] = sumc[i - 1] + c[i];
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                dp[i] = std::min(dp[i], dp[j - 1] + sumt[i] * (sumc[i] - sumc[j - 1]) + s * (sumc[n] - sumc[j - 1]));
            }
        }
        printf("%lld\n", dp[n]);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}

增强版

如果 nn 的范围扩大至 n≤3×105n \le 3 \times 10 ^ 5，此时又要如何解决呢

观察转移方程，可以发现：

dpi=min⁡1≤k≤i{dpk−1+∑k≤p≤ifp×∑1≤p≤itp+∑k≤p≤nfp×s}=min⁡1≤k≤i{dpk−1+(sumFi−sumFk−1)×sumTi+(sumFn−sumFk−1)×s}=min⁡1≤k≤i{dpk−1+sumFi×sumTi−sumFk−1×sumTi+sumFn×s−sumFk−1×s}=min⁡1≤k≤i{dpk−1+sumFi×sumTi−sumFk−1×(sumTi+s)+sumFn×s}\begin{aligned} dp_{i} & = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1} + \sum \limits_{k \le p \le i} f_p \times \sum \limits_{1 \le p \le i} t_p + \sum \limits_{k \le p \le n} f_p \times s \right\rbrace \\ & = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1} + \left(sumF_i - sumF_{k - 1}\right) \times sumT_{i} + \left(sumF_n - sumF_{k - 1}\right) \times s \right\rbrace \\ & = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1} + sumF_i \times sumT_{i} - sumF_{k - 1} \times sumT_{i} + sumF_n \times s - sumF_{k - 1} \times s \right\rbrace \\ & = \min \limits_{1 \le k \le i} \left\lbrace dp_{k - 1} + sumF_i \times sumT_{i} - sumF_{k - 1} \times (sumT_{i} + s) + sumF_n \times s \right\rbrace \\ \end{aligned}

去掉 min⁡\min ，进行移项可得：

dpk−1=dpi−sumFi×sumTi+sumFk−1×(sumTi+s)−sumFn×sdp_{k - 1} = dp_i - sumF_i \times sumT_{i} + sumF_{k - 1} \times (sumT_{i} + s) - sumF_n \times s

现在整个式子变成了 y=kx+by = kx + b 的形式

我们的目标是最小化 dpidp_i，也就是最小化 dpi−sumFi×sumTi−sumFn×sdp_i - sumF_i \times sumT_{i} - sumF_n \times s

我们把 dpk−1dp_{k - 1} 看作因变量，sumFk−1sumF_{k - 1} 看作自变量，那么我们现在在做的等价于给定若干个点 (sumFk−1,dpk−1)(sumF_{k - 1}, dp_{k - 1})，和一条已知斜率为 sumTi+ssumT_i + s 的直线，需要找这条直线在向上平移的过程中遇到的第一个点

显然，只有在点 (sumFk−1,dpk−1)(sumF_{k - 1}, dp_{k - 1}) 组成的下凸包中的点才可能是遇到的第一个点，每次遇到的第一个点就是下凸包中相邻两点组成的直线的斜率第一个大于 sumTi+ssumT_i + s 的位置

那么由于 sumTi+ssumT_i + s 单调递增，所以我们每次需要的直线的斜率也单调递增

那么我们维护一个单调队列，队列中相邻两点组成的直线的斜率单调递增，并且每个点的横坐标也单调递增，我们每次把在队首并且斜率小于 sumTi+ssumT_i + s 的点弹出队列，然后使用队首更新答案，最后将当前点插入队列，即可解决问题

由于每个点至多进出队一次，每次转移的均摊时间复杂度为 O(1)O(1)

总的时间复杂度为 O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 3e5 + 5;
    int n, s;
    LL t[MAXN], c[MAXN];
    LL sumt[MAXN], sumc[MAXN];
    LL dp[MAXN];
    struct Point
    {
        LL x, y;
        Point(LL _x = 0, LL _y = 0) : x(_x), y(_y) {}
    };
    std::deque<Point> q;
    double slope(Point x, Point y)
    {
        return (double)(x.y - y.y) / (x.x - y.x);
    }
    int main()
    {
        scanf("%d%d", &n, &s);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld", &t[i], &c[i]);
            sumt[i] = sumt[i - 1] + t[i], sumc[i] = sumc[i - 1] + c[i];
        }
        q.push_back(Point(0, 0));
        for (int i = 1; i <= n; i++)
        {
            while (q.size() >= 2 && slope(q[0], q[1]) < sumt[i] + s)
            {
                q.pop_front();
            }
            if (!q.empty())
            {
                dp[i] = q.front().y + sumt[i] * sumc[i] - (sumt[i] + s) * q.front().x + s * sumc[n];
            }
            while (q.size() >= 2 && slope(Point(sumc[i], dp[i]), q[q.size() - 1]) < slope(q[q.size() - 1], q[q.size() - 2]))
            {
                q.pop_back();
            }
            q.push_back(Point(sumc[i], dp[i]));
        }
        printf("%lld\n", dp[n]);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}