AcWing 300. 任务安排1
原题链接
中等
作者:
洛白さん
,
2022-07-04 17:18:18
,
所有人可见
,
阅读 213
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010;
int n, m;
LL f[N], s[N], x[N];
int main(){
memset(f, 0x3f, sizeof f);
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) {
cin >> s[i] >> x[i];
s[i] += s[i - 1], x[i] += x[i - 1];
}
f[0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 0; j < i; j ++){
f[i] = min(f[i], f[j] + s[i] * (x[i] - x[j]) + m * (x[n] - x[j]));
}
}
cout << f[n] << endl;
return 0;
}