80pts求助
查看原帖
80pts求助
738474
Erine楼主2022/12/17 17:57
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 3e5 + 10;

int n;
int s;
int t[maxn];
int f[maxn];
int p[maxn];
int dp[maxn];
int q[maxn];
int tl;

int decs(int i) {
    if (tl == 1) return dp[q[tl]] + t[i] * (f[i] - f[q[tl]]) + s * (f[n] - f[q[tl]]);
    int l = 1, r = tl, ans = r;
    while (l <= r) {
        int mid = l + r >> 1;
        if ((p[q[mid]] - p[q[mid + 1]]) >= t[i] * (f[q[mid]] - f[q[mid + 1]])) l = mid + 1;
        else r = mid - 1, ans = mid;
    }
    ans = q[ans];
    return dp[ans] + t[i] * (f[i] - f[ans]) + s * (f[n] - f[ans]);
}

signed main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> f[i];
        t[i] += t[i - 1];
        f[i] += f[i - 1];
    }
    dp[0] = 0, p[0] = 0;
    q[++tl] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = decs(i);
        p[i] = dp[i] - s * f[i];
        while (tl > 1 && (f[q[tl - 1]] - f[q[tl]]) * (p[q[tl]] - p[i]) < (f[q[tl]] - f[i]) * (p[q[tl - 1]] - p[q[tl]])) tl--;
        q[++tl] = i;
    }
    cout << dp[n] << endl;
    return 0;
}
2022/12/17 17:57
加载中...