백준 20180번 Two Buildings

문제 요약

n개의 빌딩의 높이 $h_i$가 주어진다.

이 때, $(h_i+h_j)(j-i), (i \le j)$의 최댓값을 구해야 한다.

n은 최대 100만이고, 주어지는 높이의 최대도 100만이다.

풀이

두 개의 점의 집합을 정의하자.
$$
P={(i,-h_i)}, Q={(i,h_i)}
$$
그러면 이제 이 문제는 집합 $P$의 점을 왼쪽 아래로 하고, 집합 $Q$의 점을 오른쪽 위로 하는 직사각형 중에서 최대 넓이를 가지는 직사각형의 넓이를 구하는 문제와 동치가 된다.

그러면 이 문제는 백준 14636번 Money for Nothing과 동일한 문제가 된다. 이제 문제를 풀 수 있다. 풀이 링크

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

int N, M;
vector<pair<ll, ll>> P, C;
vector<pair<ll, ll>> L, U;
ll dp[1000005];
ll mx;
void solve(int s, int e, int optl, int optr) {
    if (s > e) return;
    int mid = (s + e) >> 1;
    int opt = optl;
    ll& ans = dp[mid];
    ans = -2e18;
    for (int i = optl; i <= optr; ++i) {
        ll dt = U[i].second - L[mid].second;
        ll dp = U[i].first - L[mid].first;
        if (dt >= 0 || dp >= 0) {
            ll val = dt * dp;
            if (ans <= val) {
                ans = val; opt = i;
            }
        }
    }
    solve(s, mid - 1, optl, opt);
    solve(mid + 1, e, opt, optr);
    mx = max(mx, ans);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N;++i) {
        ll x; cin >> x;
        P.push_back({i,x});
        C.push_back({i,-x});
    }
    sort(P.begin(), P.end());
    sort(C.begin(), C.end());
    for (int i = 0; i < N; ++i) {
        if(L.empty() || L.back().second > C[i].second) L.push_back(C[i]);
    }
    for (int i = 0; i < N; ++i) {
        while (!U.empty() && U.back().second <= P[i].second) U.pop_back();
        U.push_back(P[i]);
    }
    // memset(dp, -1, sizeof(dp));
    solve(0, L.size() - 1, 0, U.size() - 1);
    cout << max(0LL,mx) << '\n';
    return 0;
}