python/TangDou/AcWing/ConvexHullTrick/300_1.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5010;
int n;   // n个任务
LL s;    // 等待时间
LL c[N]; // 每个任务都有一个花费，   用c[i]来表示,更新概念为前缀和
LL t[N]; // 每个任务都有一个执行时间,用t[i]来表示,更新概念为前缀和
LL f[N]; // 前i个任务，不管划分多少个阶段，最小代价是多少

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

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

    for (int i = 1; i <= n; i++)    // 从小到大枚举每个任务
        for (int j = 0; j < i; j++) // j:前一个批次的最后一个位置
            f[i] = min(f[i], f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]));
    // 输出
    cout << f[n] << endl;
    return 0;
}