[SDOI 2012]任务安排

Description

题库链接

给定 \(n\) 个任务，第 \(i\) 个任务有两个参数 \(T_i, C_i\)，你现在要将这些任务分为相邻的若干段，每一段任务需要同时完成。一段任务的用时为 \(\sum T_i+s\)（\(s\) 给定），这一段任务会同时结束。依次执行每一段划分好的任务。每一个任务的花费为该任务的结束时刻 \(\times C_i\)。问所有划分中，最少花费和。

\(1\leq n\leq 3\times 10^5, 1\leq s\leq 2^8,0\leq |T_i|,C_i\leq 2^8\)

Solution

将 \(T, C\) 分别做前缀和后，设 \(f_i\) 为 \(1\sim i\) 个任务划分好后最少的花费。可以列出转移方程 \[f_i=\min\{f_j+T_i(C_i-C_j)+s(C_n-C_j)\}\]

移项，可得 \(sC_j-f_j=-T_iC_j+(T_iC_i+sC_n-f_i)\)，要最小化 \(f_i\)，即最大化截距。因此将 \((C_j, sC_j-f_j)\) 这些点描绘在二维平面上后，去找到上凸包上与斜率为 \(-T_i\) 的直线相切的点，这一点即为最优决策点。

由于 \(-T_i\) 不满足单调性，因此需要在凸包上二分。

Code

#include 
#define y(i) (1ll*s*c[i]-f[i])
#define x(i) (1ll*c[i])
#define ll long long
using namespace std;
const int N = 3e5+5;

int n, s, t[N], c[N], q[N], head, tail;
ll f[N];

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &t[i], &c[i]),
            t[i] += t[i-1], c[i] += c[i-1];
    for (int i = 1; i <= n; i++) {
        int l = head, r = tail-1, ans = tail, m;
        while (l <= r) {
            m = (l+r)>>1;
            if ((y(q[m])-y(q[m+1])) >= -1ll*t[i]*(x(q[m])-x(q[m+1]))) ans = m, r = m-1;
            else l = m+1;
        }
        int j = q[ans];
        f[i] = f[j]+1ll*t[i]*(c[i]-c[j])+1ll*s*(c[n]-c[j]);
        while (head < tail && (y(i)-y(q[tail-1]))*(x(i)-x(q[tail])) <= (y(i)-y(q[tail]))*(x(i)-x(q[tail-1]))) --tail;
        q[++tail] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}