TIOJ 1676 烏龜疊疊樂 題解

TIOJ 1676

題序

解法

Code

#define MAXN 500005
#define MAXM 1000005 
int n, k;
int x[MAXN], pre[MAXN], dp[MAXN];

struct Line {
    int a, b;
    int operator ()(int _x) {
        return a * _x + b;
    }
};

bool check(Line l1, Line l2, Line l3, int _x) {
    // double v12 = (l1.b - l2.b) / (l2.a - l1.a);
    // double v23 = (l2.b - l3.b) / (l3.a - l2.a);
    // return v12 >= v23
    return ((l1.b - l2.b) * (l3.a - l2.a) > (l2.a - l1.a) * (l2.b - l3.b) && (_x + k) * (l3.a - l2.a) > (l2.b - l3.b));
}

void sol() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    reverse(x + 1, x + n + 1);
    for (int i = 1; i <= n; i++)   
        pre[i] = pre[i - 1] + x[i];

    deque<pair<Line, int>> dq;
    dq.push_back({{0, 0}, 0});

    for (int i = 1; i <= n; i++) {
        while (dq.size() && dq.front().S < i - k)
            dq.pop_front();
        while (dq.size() >= 2 && dq[0].F(i) < dq[1].F(i))
            dq.pop_front();

        dp[i] = -i * i + dq.front().F(i);

        Line now = {2 * i, dp[i] - i * i + pre[i]};
        while (dq.size() >= 2 && check(dq[dq.size() - 2].F, dq[dq.size() - 1].F, now, dq[dq.size() - 2].S))
            dq.pop_back();
        dq.push_back({now, i});
    }
    cout << dp[n] << endl;
}