백준 5254번 Balls

문제 요약

공의 받침대가 N개 있고 그 받침대들의 바로 위에 공이 1개씩 존재한다. 각 받침대에 공이 하나 떨어질 경우에 얻을 수 있는 점수 $c_i$가 주어진다.

이 때, 얻을 수 있는 점수는 $\sum c_i$로 trivial 하다. 여기서 장애물을 하나 둘건데 둘 수 있는 장애물은 두 종류가 있다.

하나는 특정 [l, r]에 놓고 해당 구간에 있는 공들을 전부 l로 떨어뜨릴 수 있다.

다른 하나는 [l, r]에 놓고 해당 구간에 있는 공들을 전부 r로 떨어뜨릴 수 있다.

이런 식으로 장애물을 놓을 수 있을 때, 첫번째 장애물을 하나 놓았을 때의 최대 점수값, 두번째 장애물을 하나 놓았을 때의 최대 점수값을 각각 구하는 것이 문제에서 원하는 것이다.

풀이

먼저 구간의 공들을 오른쪽으로 모아주는 장애물에 대해서 생각해보자. 왼쪽으로 모아주는 장애물에 대해서는 배열을 뒤집으면 똑같은 상황이다.

$p_i$를 1부터 i까지의 prefix sum이라고 하자. 그렇게 하면 [l,r]에 장애물을 놓았을 때의 점수는 $p_N + (r-l+1)*c_r - \sum_l^r c_i$가 된다.

장애물을 놓을 왼쪽 점을 고정하는 방식으로 생각해서 다음과 같은 dp식을 생각해보자.
$$
\begin{aligned}
dp(i) &= \text{(장애물을 i번째 받침대의 왼쪽 끝에 놓는 경우 최대 점수)} \\
dp(i) &= \underset{j>i}{max}(c_j(j-i+1)-(p_j - p_{i-1})+p_N) \\
&= \underset{j>i}{max}(-c_ji+c_jj+c_j-p_j+p_{i-1}+p_N) \\
&= \underset{j>i}{max}(-c_ji + p_N+p_{i-1}-p_{j-1}+c_jj)
\end{aligned}
$$

Convex Hull Trick을 사용할 수 있는 꼴이 나왔다.

N-1부터 i까지 돌면서 dp값을 구해주면 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

ll c[300005];
ll psum[300005];
int N;

ll get_slope(int i) {
    return -c[i];
}

ll get_bias(int i) {
    return psum[N] - psum[i-1] + c[i]*i;
}

ll solve() {
    for(int i=1;i<=N;++i) psum[i] = psum[i-1] + c[i];
    ll ret = -1e18;
    LineContainer max_hull;
    max_hull.add(get_slope(N), get_bias(N));
    for(int i=N-1;i>0;--i) {
        ret = max(ret, max_hull.query(i) + psum[i-1]);
        max_hull.add(get_slope(i), get_bias(i));
    }
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=1;i<=N;++i) cin >> c[i];
    cout << solve() << '\n';
    reverse(c+1, c+N+1);
    cout << solve() << '\n';
    return 0;
}