题目描述

有N个固定顺序的任务，每个任务都有执行所需的时间和花费。
我们需要将其划分为若干个批次，每个批次的花费为：次批次最后一个任务完成时间 * 批次所有任务花费
每个批次开始执行前都有一个启动时间S

样例

5 -》N
1 -》S
1 3 -》时间、花费
3 2
4 3
2 3
1 4

最小花费：划分为三个批次(1, 3)、(4, 2)和1
153 = (3 + 2) * 5 + (3 + 3) * 12 + 4 * 14

任务安排1 – 费用提前计算思想

1)、考虑到1s的启动时间可以提前计算可简化为：(3+2)*4 + 1*(3+2+3+3+4) + (3+3)*10 + 1*(3+3+4) + 4*11 + 1*4 = 153
2)、f[i]表示前i个任务的最小费用，则f[i] = min(f[j] + ti(ci - cj) + s(cn - cj))

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
s = int(input())
t, c = [0] * (n + 1), [0] * (n + 1)

for i in range(1, n + 1):
    t[i], c[i] = map(int, input().split())
    t[i] += t[i - 1]
    c[i] += c[i - 1]

f = [float('inf')] * (n + 1)
f[0] = 0
for i in range(1, n + 1):
    for j in range(i):
        f[i] = min(f[i], f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]))

print(f[n])

任务安排2 – 单调队列的斜率优化

1、方程变形

1)、将i、j分离：f[i] = S*cn + ti*ci + min(f[j] - (S + ti) * cj)
2)、对于直线方程b = y + kx, (y = f[j], k = S + ti, x = cj)
3)、由于k和x均为单调递增，因此可通过单调队列维护

2、维护

1)、维护对头（左图）：由于绿色圈内的点构成的斜率小于当前红色线的斜率，故其一定不可能构成答案
2)、维护队尾（右图）：红色圈内的点由于斜率大于橙色线（新加入点构成的线），故其一定不会是答案

3、总结

1)、删除不满足的点，保证队友一定是答案
2)、通过对头更新答案
3)、删除由于新入点导致的队尾不满足的点，保证时间复杂度

import sys
from collections import deque
input = lambda: sys.stdin.readline().strip()

n = int(input())
S = int(input())
t, c = [0] * (n + 1), [0] * (n + 1)
for i in range(1, n + 1):
    t[i], c[i] = map(int, input().split())
    t[i] += t[i - 1]
    c[i] += c[i - 1]

f, q = [float('inf')] * (n + 1), deque([0])
f[0] = 0
for i in range(1, n + 1):
    # 维护对头
    while len(q) >= 2 and (f[q[1]] - f[q[0]]) < (S + t[i]) * (c[q[1]] - c[q[0]]):
        q.popleft()

    # 更新答案
    j = q[0]
    f[i] = f[j] + t[i] * (c[i] - c[j]) + S * (c[n] - c[j])

    # 维护队尾
    while len(q) >= 2 and (f[q[-1]] - f[q[-2]]) * (c[i] - c[q[-1]]) > (f[i] - f[q[-1]]) * (c[q[-1]] - c[q[-2]]):
        q.pop()
    q.append(i)

print(f[n])

任务安排3 – 二分的斜率优化

1)、由于时间存在负数，因此斜率k = S + ti可能不再是单调递增，即后面的点可能构成小斜率
2)、对于对头，不能直接删除，因为大斜率可能变为小斜率，导致误删
3)、对于队尾，没有影响

import sys
from collections import deque

input = lambda: sys.stdin.readline().strip()
n, s = map(int, input().split())
t, c = [0] * (n + 1), [0] * (n + 1)

for i in range(1, n + 1):
    t[i], c[i] = map(int, input().split())
    t[i] += t[i - 1]
    c[i] += c[i - 1]

f, q = [0] * (n + 1), deque([0])
for i in range(1, n + 1):
    l = 0; r = len(q) - 1
    while l < r:
        mid = (l + r) >> 1
        if (f[q[mid + 1]] - f[q[mid]]) > (s + t[i]) * (c[q[mid + 1]] - c[q[mid]]):
            r = mid
        else:
            l = mid + 1
    j = q[r]
    f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j])

    while len(q) >= 2 and (f[q[-1]] - f[q[-2]]) * (c[i] - c[q[-2]]) >= (f[i] - f[q[-2]]) * (c[q[-1]] - c[q[-2]]):
        q.pop()
    q.append(i)

print(f[n])

运输小猫

1、解析

• 考虑能否转换成任务安排类似的情况，假设D为距离前缀和，饲养员出发时刻t，则第i只小猫能被接走的条件为：$t >= T(i)-D(i)$，现设$a(i)=T(i)-D(i)$并排序，则小猫被接走的等待时间呈现升序。题意转换为：对固定的小猫序列，将其划分为若干段，每段由一位饲养员接走，求最少等待时间
• 对于一段小猫序列，要想这段等待时间最短，则饲养员出发时刻应该是这一段的最后一只小猫
• f[i][j]表示派出i位饲养员，且接走j只小猫的所有方案
• $f[i][j] = min(f[i][j], f[i-1][k] + \sum_{x=k+1}^{j}(a_j - a_x))$

2、优化

• 化简公式：$f[i][j] = j\times a_j - s_j + min\{f[i - 1][k] + s_k - a_j\times k\}$
• 对于直线方程b = y - kx，有$y=f[i-1][k] + s_k, k=a_j, x=k$

3、代码

import sys
from collections import deque
input = lambda: sys.stdin.readline().strip()

def get(i, k):
    return f[i - 1][k] + s[k]

n, m, p = map(int, input().split())
d = [0, 0] + list(map(int, input().split()))
a = []
for i in range(1, n + 1):
    d[i] += d[i - 1]
for _ in range(1, m + 1):
    h, t = map(int, input().split())
    a.append(t - d[h])
a.sort()
a, s = [0] + a, [0] * (m + 1)
for i in range(1, m + 1):
    s[i] = s[i - 1] + a[i]

f = [[float('inf')] * (m + 1) for _ in range(p + 1)]
for i in range(p + 1):  # 一只小猫都没有，没有等待时间
    f[i][0] = 0
for i in range(1, p + 1):
    q = deque([0])
    for j in range(1, m + 1):
        while len(q) >= 2 and (get(i, q[1]) - get(i, q[0])) <= a[j] * (q[1] - q[0]):
            q.popleft()

        k = q[0]
        f[i][j] = j * a[j] - s[j] + f[i - 1][k] + s[k] - a[j] * k

        while len(q) >= 2 and (get(i, q[-1]) - get(i, q[-2])) * (j - q[-2]) >= (get(i, j) - get(i, q[-2])) * (q[-1] - q[-2]):
            q.pop()
        q.append(j)

print(f[p][m])