任务安排 3

原题链接

题目描述

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 \(T_i\)。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 \(C_i\)。

请为机器规划一个分组方案，使得总费用最小。

---

思路 二分+斜率优化DP

本题与上题的区别仅是 \(t_i\) 的取值范围。(\(-512\le t_i\le 512\))

取出上题推导公式：\(dp_i=t_i\times c_i+S\times c_n+dp_j-c_j\times(t_i+S)\)。

令 \(\begin{cases}y(j)=dp_j \\ x(j)=c_j \\ k_i=t_i+S\end{cases}\) ，可以发现 \(k_i\) 不再具有单调性。

但是，“下凸壳上的点集，相邻两点构成的斜率是单调递增的”。

我们可以维护一个下凸壳的点集，利用其的单调性，对于 \(k_i\) 找到大于他的最小值即可，可以利用单调性进行二分查找。

虽然斜率不再具有单调性，但是每个新加入的点的横坐标一定具有单调性，因为 \(1\le c_i\le 512\)，因此在插入新点的时候，可以把队尾不在凸包上的点全删。

• 查询： \(dp_{q[mid+1]}-dp_{q[mid]}\lessgtr (t_i+s)\times(c_{q[mid+1]}-c_{q[mid]})\)
• 求解： \(dp_i=t_i\times c_i+S\times c_n+dp_j-c_j\times(t_i+S)\)
• 插入： \((dp_{q[tt]}-dp_{q[tt-1]})\times(c_i-c_{q[tt - 1]})\ge(dp_i-dp_{q[tt - 1]})\times(c_{q[tt]}-c_{q[tt-1]})\)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 300010;

int n, s;
LL t[N], c[N], dp[N];
int q[N];

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

    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i++) {
        // query
        int l = hh, r = tt;
        while (l < r) {
            int mid = l + r >> 1;
            if (dp[q[mid + 1]] - dp[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid;
            else l = mid + 1;
        }
        int j = q[l];

        // get answer
        dp[i] = t[i] * c[i] + s * c[n] + dp[j] - c[j] * (t[i] + s);

        // insert
        while (hh < tt && (double)(dp[q[tt]] - dp[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >=
                (double)(dp[i] - dp[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
        q[++tt] = i;
    }

    cout << dp[n] << endl;

    return 0;
}