The secret of being a bore is to tell everything

0%

[SDOI2012]任务安排

题意

有$n (n\leq 3\times10^5)$个任务需要被完成,你可以把这些任务全部分成任意多组,每组内的任务必须连续。同组任务会在同一时刻完成,所花时间为$\sum_{i=l}^{r}t_i$,同时每组任务开始有一个预热时间$s$。任务$i$完成的费用为完成时间乘以$c_i$,求如何分组能让费用最小。

解题思路

既然要把所有任务都分组,那么我们只需要知道每个任务属于哪一个组所需费用最小即可。对于任务$i$,我们想要知道从之前哪个任务分过来费用最小。于是考虑动态规划,设$f(i)$为从$1~i$分组完成,所需的最少费用,答案则是$f(n)$。但是有个启动时间$s$不好处理,怎么办呢。利用费用提前思想,每次启动机器的时间一定会给后面的任务贡献费用,那么转移方程为:
$$
f(i) = \min_{j<i}\{f(j) + (F_i - F_j) * T_i + s * (F_n - F_j) \}
$$
式子中$F_i$表示费用的前缀和,$T_i$表示时间的前缀和。

显然暴力寻找是$O(n^2)$,但是可以用斜率优化DP的套路去降时间复杂度。考虑到费用$F_i$是单调不减的,那么显然$j$越小需要的费用越大,这就让我们想到决策可能是随着$i$增大而单调不减的,打表也证实了这一点。由于决策单调性的存在,我们的目标可以转变成计算出什么时候需要更新决策。

于是考虑此时我们在$i$,决策$j$能替换掉原有决策$k$,根据单调性此时一定有$j>k$,且
$$
f(j) + (F_i - F_j) * T_i + s * (F_n - F_j) \leq f(k) + (F_i - F_k) * T_i + s * (F_n - F_k)
$$

$$
f(j) + F_iT_i - F_jT_i + sF_n - sF_j \leq f(k) + F_iT_i - F_kT_i + sF_n - sF_k
$$
消掉不变的项
$$
f(j) - F_jT_i - sF_j \leq f(k) - F_kT_i - sF_k
$$
移项,尽量让带$T_i$的在左边,$j, k$在右边
$$
T_i(F_k - F_j) \leq f(k)- f(j) - sF_k + sF_j
$$
这里要格外小心,由于$j>k$,一定有$F_j>F_k$,即$F_k - F_j \leq 0$。此时等于$0$的情况必须特判,而小于$0$的情况需要让不等式变号!最终结果:
$$
T_i \geq \frac{f(k)- f(j) - sF_k + sF_j}{F_k - F_j}
$$
由此我们可以得出结论,令$slope(k, j) = \frac{f(k)- f(j) - sF_k + sF_j}{F_k - F_j}$。当$slope(k, j) \leq T_i$时,有$j$优于$k$(因为$j>k$所以$j$会比较靠后,是更优解),此时这个$slope(k, j)$可以看成是点$k$到点$j$的斜率。

我们进一步分析这个斜率,假设当前$j$打败了$k$,新来了一个$i > j$,如果有$slope(j, i) \leq slope(k,j)$那么此时$j$也不占优势了。因为无论后面的$T_{i+1}$值是多少,$slope(j, i)$都会比$slope(k,j)$更容易小于$T_{i+1}$,而此时$i$又比$j$打,那么$j$就再也打不过$i$了。此时清除$j$这个废物,不然整个序列就不符合后面的具有比前面更优的潜力这个性质了(即决策单调)。

整理一下得到的两个性质
$$
\begin{cases}
slope(k, j) &\leq T_i &\text{此时j替换k}\\
slope(k, j) &\geq slope(j, i) &\text{此时j比不过i}
\end{cases}
$$
根据这两个性质我们就可以写出一个单调队列,里面存储的就是位置$i$,最优决策则可以通过这两个性质取得。

1
int l = 0, r = 0;
2
for (int i = 1; i <= n; i++) {
3
    // 性质1,QQ是单调队列
4
    while (l < r && slope(QQ[l], QQ[l + 1]) <= T[i]) ++l;
5
    int opt = QQ[l];
6
    dp[i] = dp[opt] + ...
7
    // 性质2
8
    while (l < r && slope(QQ[r - 1], QQ[r]) >= slope(QQ[r], i)) --r;
9
    QQ[++r] = i;
10
}

但是仔细看这题的数据范围,$|t_i|\leq2^8$,啥意思,就是$t_i$可能是负数,也就是$T_i$并非单调增。我们的代码这一行while (l < r && slope(QQ[l], QQ[l + 1]) <= T[i]) ++l;就是基于$T_i$是单调增的情况,我们去除之前一定不会比现在更优的点。但是如果$T_i$并非单调增,被去掉点有可能在此时是最优解,于是我们只能删掉这一行。

那么问题来了,我们怎么知道哪个点是最优解呢?首先,我们利用性质1和2维护了一个斜率单调下降的序列,那么对于一个$T_i$,只要知道满足$slope(j, j+1) \leq T_i$且最大的$j+1$,就是最优解。于是我们可以使用二分。二分找指定条件的方法我在之前的博客中介绍过,这里就不多讲了。

最后一个极其重要的点就是由于这题的毒瘤性质$c_i$可以是$0$,也就是$F_j-F_k$可能是$0$,这会严重影响决策正确性。因为$slope(k, j)$此时有可能是正无穷也有可能是负无穷(因为分子不一定是正的),它们显然会干扰性质1和2。此时我们就要想,当$c_k$为$0$的时候我们是包括它还是不包括它更好呢?显然是要包括啊,免费的你还不要!也就是说,当$j>k$的时候,我们不要去替换成$j$,而是能留多久留多久,如果要替换那就直接越过$j$,此时$j$毫无卵用。于是我们最好就把$slope(j,k)$设为正无穷大,使得它无论怎样都不会成为最优解,这样就不会有错了。

时间复杂度

$O(n\log{n})$

参考代码

1
// j > k
2
double slope(int k, int j) {
3
    if (F[k] == F[j]) return 1.0 / 0.0;
4
    return (dp[k] - dp[j] + s * (double)(F[j] - F[k])) / (double)(F[k] - F[j]);
5
}
6
7
int bSearch(int l, int r, ll v) {
8
    if (l == r) return QQ[l];
9
    int ans = r;
10
    while (l <= r) {
11
        int mid = (l + r) / 2;
12
        if (slope(QQ[mid + 1], QQ[mid]) >= v)
13
            ans = mid, r = mid - 1;
14
        else
15
            l = mid + 1;
16
    }
17
    return QQ[ans];
18
}
19
20
int main() {
21
#ifdef LOCALLL
22
    freopen("in", "r", stdin);
23
    freopen("out", "w", stdout);
24
#endif
25
    n = read<ll>();
26
    s = read<ll>();
27
    for (int i = 1; i <= n; i++) {
28
        ll t = read<ll>(), c = read<ll>();
29
        T[i] = T[i - 1] + t, F[i] = F[i - 1] + c;
30
    }
31
    int l = 0, r = 0;
32
    for (int i = 1; i <= n; i++) {
33
        int opt = bSearch(l, r, T[i]);
34
        dp[i] = dp[opt] + (F[i] - F[opt]) * T[i] + s * (F[n] - F[opt]);
35
        while (l < r && slope(QQ[r - 1], QQ[r]) >= slope(QQ[r], i)) --r;
36
        QQ[++r] = i;
37
    }
38
    printf("%lld", dp[n]);
39
    return 0;
40
}