백준 14179번 크리스마스 이브

문제 요약

수직선 상에 위치한 창고들의 위치와 각 창고에 있는 선물들의 무게 $x_i, w_i$가 주어진다. 창고는 n개 존재한다.

$x_i$에 위치한 창고의 선물들 $w_i$톤을 $x_j$에 위치한 창고로 옮기는 비용은 $\vert x_i - x_j \vert w_i$만큼 들어간다.

n개의 창고들 중에서 k개를 선택해서순간이동기를 그 곳에 설치할 것이다. 그리고 모든 선물들을 k개의 창고로 나눠 옮기려고 한다. 이 때 최소 운반비용을 구해야 한다.

n, k는 최대 5000이고 $x_i, w_i$는 최대 100만이다.

풀이

바로 다음과 같은 dp식을 생각해 볼 수 있다.
$$
dp(i,j) = \text{1번부터 j번까지의 창고에서 i개를 선택했을 때의 최소 비용}
$$
$C(i,j)$를 $i$번 창고부터 $j$번 창고까지에서 1개의 창고를 선택해서 $i$번 창고부터 $j$번 창고까지의 모든 선물을 옮겼을 때의 최소 비용이라고 정의하자. 그러면 아래와 같은 점화식이 나온다.
$$
dp(i,j) = \underset{k<j}{min}(dp(i-1,k)+C(k+1, j))
$$
일단 이 C값도 나이브하게 구하면 $O(n^3)$으로 시간초과를 받는다. 그리고 $dp$의 상태전이도 나이브하게 하면 $O(kn^2)$만큼 걸린다.

$C(i,j)$부터 최적화해보자.

일단 $i \cdots j$에 존재하는 한 지점 $k$를 잡아보자. 그러면 $k$까지 모든 짐을 옮기는 데에 드는 비용$f(i,j,k)$은 아래와 같다.
$$
f(i,j,k) = \sum_{x_i<k}w_i(k-x_i) + \sum_{x_j>k}w_j(x_j-k)
$$
이제 k를 1만큼 키웠다고 해보자. 그러면 k의 왼쪽에 있는 선물들의 무게 합만큼 비용이 증가하고, k의 오른쪽에 있는 선물들의 무게 합만큼 비용이 감소하게 될 것이다.

이 점을 생각해보면 $f(i,j,k)$를 $k$에 대한 함수로 볼 수 있고, 이 함수는 아래로 볼록한 convex한 함수가 된다.

그리고 이 함수가 최소가 되는 지점은 $k$를 기준으로 왼쪽에 있는 선물들의 무게 합이 오른쪽에 있는 선물들의 무게 합보다 많아지기 직전의 지점이다.

이 점을 이용하면 $C(i,j)$는 $O(n^2)$에 모든 값을 전처리 할 수 있다.

이제 $f(i,j,k)$가 $C(i,j)$가 되게하는 $k$를 $opt_j$라고 하자. 그러면 $i$는 고정해두고 $j < j'$일 때, $opt_j \le opt_{j'}$임을 알 수 있다. 그리고 이를 통해서 $dp(i,j)$가 최소가 되게하는 $opt_j$를 생각 했을 때, $j < j'$일 때 $opt_j \le opt_{j'}$임도 알 수 있다.

따라서 분할정복 최적화를 적용할 수 있으며, 이를 통해서 $O(knlogn)$에 문제를 해결 가능하다.

long long 배열을 무턱대고 잡으니까 메모리 초과가 발생했었다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
ll distsum[5005][5005];
ll C[5005][5005];
ll dp[2][5005];
ll psum[5005];

vector<pair<ll,ll>> a;

ll f(int l, int mid, int r) {
    return distsum[mid][l] + distsum[mid][r];
}

void solve(int i, int s, int e, int opts, int opte) {
    if(s > e) return ;
    int mid = (s+e) >> 1;
    ll &ans = dp[i&1][mid];
    ans = INF;
    int opt_mid = -1;
    for(int k=opts;k<mid && k<=opte;++k) {
        ll tmp = dp[(i+1)&1][k] + C[k+1][mid];
        if(ans > tmp) {
            ans = tmp;
            opt_mid = k;
        }
    }
    solve(i, s, mid-1, opts, opt_mid);
    solve(i, mid+1, e, opt_mid, opte);
}

int N, K;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K; a.resize(N+1);
    for(int i=1;i<=N;++i) cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end());
    for(int i=1;i<=N;++i) psum[i] = psum[i-1] + a[i].second;
    for(int i=1;i<=N;++i) {
        distsum[i][i] = 0;
        for(int j=i-1;j>0;--j) distsum[i][j] = distsum[i][j+1] + a[j].second * (a[i].first - a[j].first);
        for(int j=i+1;j<=N;++j) distsum[i][j] = distsum[i][j-1] + a[j].second * (a[j].first - a[i].first);
    }
    for(int i=1;i<=N;++i) {
        int k = i; C[i][i] = 0;
        for(int j=i+1;j<=N;++j) {
            while(k<j && f(i,k,j) > f(i,k+1,j)) ++k;
            C[i][j] = f(i,k,j);
        }
    }
    for(int i=1;i<=N;++i) dp[1][i] = C[1][i];
    for(int i=2;i<=K;++i) {
        solve(i, i, N, i-1, N-1);
    }
    cout << dp[K&1][N] << '\n';
    return 0;
}