任务安排1

AcWing-300-任务安排1

分析

见《进阶指南》第322页。

实现

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

typedef long long LL;
const int N = 5010;
int n, s;
LL f[N], st[N], sc[N];

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

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= i - 1; ++ j)
            f[i] = min(f[i], f[j] + st[i] * (sc[i] - sc[j]) + s * (sc[n] - sc[j]));
    cout << f[n] << endl;
    return 0;
}