题目描述

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

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

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

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

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

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

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

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

输入格式
第一行包含整数 $N$。

第二行包含整数 $S$。

接下来 $N$ 行每行有一对整数，分别为 $T_i$ 和 $C_i$ ，表示第 $i$ 个任务单独完成所需的时间 $T_i$ 及其费用系数 $C_i$。

输出格式
输出一个整数，表示最小总费用。

数据范围
$1≤N≤3\times 10^5$,
$1≤T_i,C_i≤512$,
$0≤S≤512$

样例

input:

5
1
1 3
3 2
4 3
2 3
1 4

output:

153

算法1

(直接DP) $O(N^2)$

观察发现，$S$在费用上的累加可以转换为后缀累加，于是有转移方程：

$dp_i=\min\limits_{0\leq j < i} \{dp_j+\sum\limits_{1\leq k\leq i}T_k\cdot\sum\limits_{j < k \leq i}C_k+S\cdot\sum\limits_{j < k\leq N}C_k\}$

初始条件$dp_0=0$。

暴力枚举$j$就可以做到$O(N^2)$的复杂度。

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

#define int long long
int n, s, pret[5005], prec[5005], dp[5005];

void Read() {
    scanf("%lld%lld", &n, &s);
    for (int i = 1;i <= n;i++) {
        int t, c;
        scanf("%lld%lld", &t, &c);
        pret[i] = pret[i - 1] + t;
        prec[i] = prec[i - 1] + c;
    }
}

void Solve() {
    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] + pret[i] * (prec[i] - prec[j]) + s * (prec[n] - prec[j]));
        }
    }
    printf("%lld", dp[n]);
}

signed main() {
    Read();
    Solve();
    return 0;
}

算法2

(DP+斜优) $O(N)$

但是$O(N^2)$的复杂度仍不足以通过本题，考虑继续优化。

发现上面的DP是一个1D/1D的DP，所以考虑优化掉转移的维度。

考虑两个决策$j_1$和$j_2$满足$j_1<j_2$，且对于$dp_i$的转移满足$j_2$优于$j_1$。

设$pt_i=\sum\limits_{1\leq j\leq i} T_j$，$pc_i=\sum\limits_{1\leq j\leq i} C_j$，根据转移方程列出不等式：

$$dp_{j_1}+pt_i\cdot(pc_i-pc_{j_1})+S\cdot(pc_N-pc_{j_1}) \geq dp_{j_2}+pt_i\cdot(pc_i-pc_{j_2})+S\cdot(pc_N-pc_{j_2})$$

拆开括号，约去相同项得：

$$dp_{j_1}-pt_i\cdot pc_{j_1}-S\cdot pc_{j_1}\geq dp_{j_2}-pt_i\cdot pc_{j_2}-S\cdot pc_{j_2}$$

移项、因式分解得：

$$(pt_i+S)(pc_{j_2}-pc_{j_1})\geq dp_{j_2}-dp_{j_1}$$

因为题目保证$C_i \geq 1$，所以$pc_{j_2}-pc_{j_1}\geq 1$，再移项得：

$$T_i+S \geq \frac{dp_{j_2}-dp_{j_1}}{pc_{j_2}-pc_{j_1}}$$

因此当$j_1,j_2$满足上面的不等式时，$j_2$优于$j_1$。

设$S(j_1,j_2)=\frac{dp_{j_2}-dp_{j_1}}{pc_{j_2}-pc_{j_1}}$。

若对于一个三元组$i\leq j\leq k$满足$S(i,j)\geq S(j,k)$，则$j$必然不可能成为最优决策。

证：若$j$是最优决策，则$j$优于$i$，则必然有$T_i+S \geq S(i,j) \geq S(j,k)$。但是此时$k$优于$j$，矛盾。

所以可以维护一个类似单调队列的数组$A_{[1,m]}$，满足对于任意一个$i < m-1$，有$S(A_i,A_{i+1}) < S(A_{i+1},A_{i+2})$成立。

但是在取出队头转移之前，要先删除所有满足$T_i + S < S(A_1,A_2)$的元素，因为这些元素都不是最优决策。

时间复杂度

因为每一个元素都最多进1次队并出1次队，因此均摊时间复杂度$O(N)$。

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

int n, hd, tl;
long long s, pret[300005], prec[300005], que[300005], dp[300005];

void Read() {
    scanf("%d%lld", &n, &s);
    for (int i = 1;i <= n;i++) {
        long long t, c;
        scanf("%lld%lld", &t, &c);
        pret[i] = pret[i - 1] + t;
        prec[i] = prec[i - 1] + c;
    }
}

double Slope(int j1, int j2) {
    return ((double)dp[j2] - (double)dp[j1]) / ((double)prec[j2] - (double)prec[j1]);
}

void Solve() {
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    hd = tl = 1;
    que[tl++] = 0;
    for (int i = 1;i <= n;i++) {
        while (tl - hd > 1) {
            int a1 = que[hd], a2 = que[hd + 1];
            //cout << pret[i] + s << " " << Slope(a1, a2) << endl;
            if ((double)pret[i] + (double)s >= Slope(a1, a2)) hd++;
            else break;
        }
        int j = que[hd];
        dp[i] = dp[j] + pret[i] * (prec[i] - prec[j]) + s * (prec[n] - prec[j]);
        while (tl - hd > 1) {
            int a2 = que[tl - 1], a1 = que[tl - 2];
            if (Slope(a1, a2) >= Slope(a2, i)) tl--;
            else break;
        }
        que[tl++] = i;
        //for (j = hd;j < tl;j++) printf("%d ", que[j]);
        //printf("\n");
    }
    printf("%lld", dp[n]);
}

int main() {
    Read();
    Solve();
    return 0;
}