백준 15958번 프로도의 100일 준비

문제 요약

길이가 N인 히스토그램이 주어진다.

L-모양 직각다각형의 정의가 주어지는데 주어지는 히스토그램에서 면적이 가장 큰 L-모양 직각다각형의 면적을 출력하는 것이 문제에서 원하는 것이다.

N은 최대 50만이다

풀이

BOJ 3319번 전령들의 풀이를 알고 있는 것을 전제로 글을 작성합니다.

먼저 L-모양 직각다각형을 다루기 쉬운 형태로 바꿔봅시다. 이 직각다각형은 한 직선을 기준으로 양쪽에 직사각형 두 개가 붙은 형태로 볼 수 있습니다.

따라서, 히스토그램에서 하나의 변을 기준으로 양 옆에 직사각형이 붙어 있는 모양이 L-모양 직각다각형이 됩니다.

이제 문제는 히스토그램에서 한 변을 기준으로 해당 변에서 끝나는 가장 큰 직사각형과 해당 변에서 시작하는 가장 큰 직사각형 두 개를 찾는 문제로 바뀌었습니다. 이런 값을 모든 변에 대해서 구하고 그 값들 중에서 가장 큰 값이 답입니다.

일단 특정 변에서 시작하는 가장 큰 직사각형을 찾는 것은 특정 변에서 끝나는 가장 큰 직사각형을 찾는 것과 동치입니다. (히스토그램을 좌우로 뒤집으면 동일)

따라서, 히스토그램에서 가장 왼쪽 변을 0번째라고 하고 제일 오른쪽 변을 N번째라고 하겠습니다.

지금부터 구할 것은 i번째 변에서 끝나는 직사각형 중에서 가장 큰 직사각형의 면적입니다. 이 값을 $dp(i)$라고 합시다. $h$는 1부터 시작합니다.

$dp(i)$를 계산하기 잘 계산하기 위해서 $l_i$를 새롭게 정의합시다. 이 $l_i$는 $h_i$보다 작은 $h_j$면서 $j<i$면서 가장 큰 $j$를 말합니다. 만약에 그런 $l_i$가 없다고 하면 0입니다.

그러면 $dp(i)$는 다음과 같은 코드로 구하는 것이 가능합니다.

idx = i
while idx != 0:
    dp[i] = max(dp[i], h[idx]*(s[i]-s[l[idx]]))
    idx = l[idx]

s는 i번째 변의 위치입니다.

idx가 l[idx]를 타고 내려가게 되는데 이러한 관계를 그래프로 나타낼 수 있습니다.

0번부터 N번까지의 노드가 있고 $i$와 $l_i$가 엣지로 연결되어 있는 상태고 이 그래프는 0번이 루트인 트리가 됩니다.

이제 이 트리에서 전령들에서 했던 것을 똑같이 해주면 됩니다. 다른 것은 전령들에선 dp 값을 구한 다음에 직선을 추가했지만 이 문제에선 직선을 추가한 다음에 dp값을 구합니다.

그리고 입력 처리가 좀 귀찮습니다.

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

int N, ptr;
vector<pair<ll,ll>> h;
vector<vector<int>> G;
vector<int> start;

struct Line{
    ll m, b;
    Line() : m(0), b(0) {};
    Line(ll m_, ll b_) : m(m_), b(b_) {};
    ll f(ll x) { return m*x + b; }
};

vector<Line> lines;
ld intersect(Line &a, Line &b) {
    return (ld)(a.b - b.b)/(b.m - a.m);
}

int add_line(Line &line) {
    int lo = 0, hi = ptr;
    if(ptr == 1) return ptr;
    while(lo < hi) {
        int mid = lo + hi >> 1;
        if(intersect(lines[mid-1], line) < intersect(lines[mid], lines[mid-1])) hi = mid;
        else lo = mid+1;
    }
    return lo;
}

ll query(ll x) {
    int lo = 0, hi = ptr - 1;
    while(lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if(intersect(lines[mid], lines[mid-1]) < x) lo = mid;
        else hi = mid-1;
    }
    return lines[lo].f(x);
}

void dfs(int cur, int par, vector<ll> &dp) {
    int rb_idx, rb_ptr = ptr;
    Line rb_line;
    assert(h[cur].second * h[start[cur]].first >= 0);
    Line cur_line(h[cur].second, -h[cur].second * h[start[cur]].first);
    rb_idx = add_line(cur_line);
    rb_line = lines[rb_idx];
    lines[rb_idx] = cur_line;
    ptr = rb_idx + 1;
    dp[cur] = query(h[cur].first);
    for(auto &nxt:G[cur]) {
        if(nxt == par) continue;
        dfs(nxt, cur, dp);
    }
    lines[rb_idx] = rb_line;
    ptr = rb_ptr;
}

void make_tree() {
    stack<pair<ll,ll>> st;
    st.emplace(0,0);
    for(int i=1;i<=N;++i) {
        while(!st.empty() && st.top().second >= h[i].second) st.pop();
        start[i] = st.top().first;
        G[start[i]].push_back(i);
        G[i].push_back(start[i]);
        st.push(make_pair(i, h[i].second));
    }
}

vector<ll> solve() {
    G.clear(); start.clear(); lines.clear();
    G.resize(N+1, vector<int>()); start.resize(N+1, 0);
    lines.resize(N+1, Line()); ptr = 0;
    vector<ll> dp(N+1, 0);
    make_tree();
    dfs(0,0,dp);
    return dp;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    vector<pair<ll,ll>> v(N);
    for(int i=0;i<N;++i) cin >> v[i].first >> v[i].second;
    ll x = 0;
    h.emplace_back(0,0);
    for(int i=1;i<N;++i){ 
        if(x != v[i].first) {
            h.push_back(v[i]);
            x = v[i].first;
        }
    }
    v.clear();
    N = h.size() - 1;
    vector<ll> dp1 = solve();
    ll pivot = h.back().first;
    for(int i=0;i<N;++i) {
        h[i].first = pivot - h[i].first;
        h[i].second = h[i+1].second;
    }
    h[N] = make_pair(0,0);
    reverse(h.begin(), h.end());
    vector<ll> dp2 = solve();
    ll ans = 0;
    for(int i=0;i<=N;++i) ans = max(ans, dp1[i]+dp2[N-i]);
    cout << ans << '\n';
    return 0;
}