백준 25404번 주차 타워

문제 링크

$dp[x][e]$를 $x$번 자동차까지 해결한 상태에서, $e$번 칸이 가장 아래에 있을 때의 최소 비용이라고 정의하자.

\(dp[x][e] = \min_s(dp[x-1][s] + C(s, e, x))\) \(C(s, e, x) = \text{x를 모두 지나며 s에서 시작해 e에서 끝내는 최소 비용}\)

이렇게 하면 $\mathcal{O}(N^3)$에 해결할 수 있다.

그러나 $dp[x][e]$를 모든 $e$에 대해 구할 필요는 없다. 자동차 번호 $x$가 놓여 있는 칸들에 대해서만 $e$를 고려하면 충분하다. 그러면 $\mathcal{O}(N^2)$에 해결할 수 있다.

전파를 잘하면 $\mathcal{O}(N \log N)$에 해결할 수 있다. 자동차 번호를 좌표 압축한 후, 배열을 두 번 이어 붙여 일자로 펼쳐 이를 $a$라고 하자. 번호가 $x$인 자동차들을 $a$에서 연속하게 모두 골라 양끝 인덱스를 $l, r$이라 하자. 이동 경로는 항상 $s \rightarrow [l, r] \rightarrow e$로 표현된다. $[l, r]$을 고정한 후 어떻게든 전파하면 된다. 세그먼트 트리를 써도 되고, DP를 이용해도 된다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 101010;

int N, a[MAXN];
vector<int> car[MAXN];
map<int, ll> dp[MAXN];

int main()
{
    cin >> N;
    vector<int> v;
    for(int i = 0; i < N; i++) cin >> a[i], v.push_back(a[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < N; i++) {
        int idx = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        car[idx].push_back(i);
        car[idx].push_back(i+N);
        dp[idx][i] = 1e18;
        dp[idx][i+N] = 1e18;
    }
    dp[0][0] = dp[0][N] = 0;

    for(int i = 1; i <= v.size(); i++) {
        sort(car[i].begin(), car[i].end());
        int l = 0;
        int r = ssize(car[i]) / 2 - 1;
        for(; r < car[i].size(); l++,r++) {
            ll mn = 1e18;
            auto it = dp[i-1].lower_bound(car[i][l]);
            if(it != dp[i-1].end()) mn = min(mn, abs(it->first - car[i][l]) + it->second);
            if(it != dp[i-1].begin()) --it, mn = min(mn, abs(it->first - car[i][l]) + it->second);
            dp[i][car[i][r]] = min(dp[i][car[i][r]], car[i][r] - car[i][l] + mn);

            mn = 1e18;
            it = dp[i-1].lower_bound(car[i][r]);
            if(it != dp[i-1].end()) mn = min(mn, abs(it->first - car[i][r]) + it->second);
            if(it != dp[i-1].begin()) --it, mn = min(mn, abs(it->first - car[i][r]) + it->second);
            dp[i][car[i][l]] = min(dp[i][car[i][l]], car[i][r] - car[i][l] + mn);
        }

        for(auto [k, item] : dp[i]) {
            if(dp[i].contains(k+N)) dp[i][k+N] = min(dp[i][k+N], item);
            if(dp[i].contains(k-N)) dp[i][k-N] = min(dp[i][k-N], item);
        }

        for(auto it = dp[i].begin(); it != dp[i].end(); ++it) {
            if(it != dp[i].begin()) {
                auto j = it; --j;
                j->second = min(j->second, it->second + it->first - j->first);
            }
            auto j = it; ++j;
            if(j != dp[i].end()) {
                j->second = min(j->second, it->second + j->first - it->first);
            }
        }

        for(auto it = dp[i].rbegin(); it != dp[i].rend(); ++it) {
            if(it != dp[i].rbegin()) {
                auto j = it; --j;
                j->second = min(j->second, it->second - it->first + j->first);
            }
            auto j = it; ++j;
            if(j != dp[i].rend()) {
                j->second = min(j->second, it->second - j->first + it->first);
            }
        }

        for(auto [k, item] : dp[i]) {
            if(dp[i].contains(k+N)) dp[i][k+N] = min(dp[i][k+N], item);
            if(dp[i].contains(k-N)) dp[i][k-N] = min(dp[i][k-N], item);
        }

        // for(auto [k, item] : dp[i]) {
        //     cout << format("dp[{}][{}] = {}\n", i, k, item);
        // }
    }

    ll mn = 1e18;
    for(auto [k, i] : dp[v.size()]) mn = min(mn, i);
    cout << mn;
}