AcWing 300.任务安排

一、样例说明

样例：
5个任务，每个任务的启动时间是1
1 3 4 2 1
3 2 3 3 4

如果我们把前3个任务看成一批，后2个任务看成一批。
那么
第一批时间点：1+3+4=8 完成这批任务需要8个时间,外加上一个批次启动的时间1，就是共9个时间

第二批时间点：2+1=3 完成这批任务需要3个时间，外加上一个批次启动的时间1，就是4个时间，所以第二个时间点就是9+4=13

接下来算费用:
第一批的费用总和是3+2+3=8 总的花费就是 8*9=72

第二批的费用总和是3+4=7 7*13=91

72+91=163

最优解是153，看来这么划分不是最优解,好，题目理解完毕。

二、解题思路

使用费用提前计算的思想, 考虑当前批的子任务, 所需要的启动时间\(S\), 该启动时间会累计到此后所有任务的完成时刻.

状态定义
\(f[i]\)表示将前\(i\)个任务分成若干批执行的最小费用

转移方程
\(f[i]=min(f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[N]-sumC[j])\)

其中第\(j+1\)至\(i\)个任务在同一批次内完成

算法设计
设置二重循环, 时间复杂度为\(O(N^2)\)
循环1: 设置子批次以第\(i\)个任务为结尾
循环2: 设置子批次以第\(j\)个任务为开始, 其中\(0
\(f[i]=min(f[i]\), 转移方程计算结果)

三、实现代码

#include 

using namespace std;
typedef long long LL;
const int N = 5010;

int n;
LL s;      //等待时间
LL sc[N];  //每个任务都有一个花费，用c[i]来表示，sc[i]就是前缀和
LL st[N];  //每个任务都有自己的执行时间t[i],前缀和就是st[i]
LL f[N];

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        LL t, c;
        cin >> t >> c;
        st[i] = t + st[i - 1];
        sc[i] = c + sc[i - 1];
    }

    //初始化
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    //n^2级的时间复杂度
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] = min(f[i], f[j] + st[i] * (sc[i] - sc[j]) + s * (sc[n] - sc[j]));
    //输出
    printf("%lld\n", f[n]);
    return 0;
}