백준 4008번 특공대

문제 요약

길이 N의 배열이 주어진다. 연속된 하나의 구간의 점수는 다음과 같이 정의된다.

해당 구간에 속하는 수들듸 합을 $x$라고 하자. 그러면 그 연속구간의 점수는 $ax^2+bx+c$가 된다.

이제 길이 N의 배열을 연속된 구간들로 쪼갤 건데 쪼갤 경우 각 구간들의 점수 합의 최대를 구하여라

N은 최대 100만이다.

풀이

다음과 같은 dp 식을 세워볼 수 있다.
$$
\begin{aligned}
dp(i) &= \text{1부터 i까지 구간들로 나눴을 때의 최댓값} \\
dp(i) &= \underset{j<i}{max}(dp(j)+ax^2+bx+c), \quad x=p_i-p_j
\end{aligned}
$$
여기서 $p_i$는 1부터 i까지의 prefix sum을 나타낸다. $x$자리에 대입하면 아래와 같은 식이 나온다.
$$
dp(i) = \underset{j<i}{max}(-2ap_jp_i+ap_j^2-bp_j+dp(j))+ap_i^2+bp_i+c
$$
이러한 식은 Convex Hull Trick을 사용할 수 있는 꼴이 됐다. 이는 $O(NlogN)$으로 해결이 가능하다.

a는 음수고, $p_j$는 prefix sum이기 때문에 단조 증가한다. 즉, dp식 안에 있는 기울기가 단조 증가하는 형태이다. 그리고 $x$값으로 사용되는 $p_i$도 단조 증가하기 때문에 해당 문제는$O(N)$으로 해결 가능하다.

LineContainer와 같아 Dynamic Convex Hull Trick을 Multiset으로 해결하는 경우 메모리 초과를 받을 수도 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e10;
int N;
ll a[1000005], pre[1000005], dp[1000005];
ll A, B, C;
int ptr;
struct Line {
    ll m, b;
    double x;
    Line(ll _m, ll _b, double _x) : m(_m), b(_b), x(_x) {};
    ll f(ll x) {
        return m * x + b;
    }
};
vector<Line> lines;

double intersect(Line& a, Line& b) {
    return (double)(b.b - a.b) / (a.m - b.m);
}

void addLine(ll m, ll b) {
    Line a(m, b, -INF);
    if (lines.empty()) {
        lines.push_back(a);
        return;
    }
    while (!lines.empty()) {
        Line top = lines.back();
        double x = intersect(top, a);
        if (x <= top.x) lines.pop_back();
        else break;
    }
    a.x = intersect(lines.back(), a);
    lines.push_back(a);
    if (ptr >= lines.size()) ptr = lines.size() - 1;
    return;
}

ll query(ll x) {
    while (ptr < lines.size() - 1 && lines[ptr + 1].x < x) ++ptr;
    return lines[ptr].f(x);
}

ll f(ll x) {
    return A * x * x + B * x + C;
}

ll slope(int i) {
    return -2 * A * pre[i];
}

ll inter(int i) {
    return A * pre[i] * pre[i] - B * pre[i] + dp[i];
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    cin >> A >> B >> C;
    for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int i = 1; i <= N; ++i) pre[i] = pre[i - 1] + a[i];
    dp[1] = f(pre[1]);
    addLine(slope(1), inter(1));
    for (int i = 2; i <= N; ++i) {
        dp[i] = max(f(pre[i]), query(pre[i]) + f(pre[i]));
        addLine(slope(i), inter(i));
    }
    cout << dp[N] << '\n';
    return 0;
}