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;
}