任务安排 1

原题链接

题目描述

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

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

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

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

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

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

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

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

---

思路 斜率优化DP+前缀和

根据题意，我们需要求出 每批任务的结束时刻 \(\times\) 该批任务的花费总和。即 \(\sum t\times \sum c\)。

Note

需要注意的是，每次新增一批任务之后，该批的启动时间 \(S\) 会影响后续所有任务的结束时间，这里采用花费提前计算的思想，即将 \(S\) 对后续的影响放在下一批任务内，而不需要依次考虑后续所有批次的任务。

由于需要快速求出一段区间的 时间 \(sumc\) 和 花费 \(sumt\) 的 和，我们可以采用前缀和优化来快速求出。

状态定义： \(dp[i]\) 前 \(i\) 个任务分批完成的方案集合。

状态属性： 最小值。

状态计算： \(dp[i]=\min\{dp[j]+sumt[i]\times(sumc[i]-sumc[j])+S\times(sumc[n]-sumc[j])\}_{(0\le j\le i-1)}\)

---

代码

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

typedef long long LL;

const int N = 5010;

int n, S;
LL sumc[N], sumt[N];
LL dp[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 >> sumt[i] >> sumc[i];
        sumt[i] += sumt[i - 1];
        sumc[i] += sumc[i - 1];
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i], dp[j] + sumt[i] * (sumc[i] - sumc[j]) + S * (sumc[n] - sumc[j]));

    cout << dp[n] << endl;

    return 0;
}