백준 13261번 탈옥

문제 요약

크기가 L인 배열 C가 주어집니다. 이 배열을 G개의 연속적인 구간으로 나누려고 합니다.

하나의 구간이 [s, e]라고 하면 해당 구간의 점수는 $(C_s+C_{s+1}+\cdots+C_e)(e-s+1)$로 정의됩니다.

이 때 구간을 잘 나눴을 때 모든 구간의 점수의 합 중에서 최솟값을 구해야 합니다.

이 때, L은 최대 8,000이고 G는 최대 800입니다.

풀이

다음과 같은 dp식을 생각해봅시다.
$$
\begin{gather}
dp(i,j) = \text{[1,j]를 i개의 연속구간으로 나눴을 떄의 최솟값} \\
dp(i,j) = \underset{k<j}{min}(dp(i-1,j-k)+C(j-k+1,j)) \\
C(s, e) = (c_s+c_{s+1}+\cdots+c_e)(e-s+1)
\end{gather}
$$
원하는 값은 dp(G, L)입니다. 나이브하게 구하면 $O(GL^2)$로 시간초과 입니다.

여기서 cost함수인 $C$를 살펴봅시다.
$$
a \le b \le c \le d, C(a,c)+C(b,d) \le C(a,d)+C(b,c)
$$
위 부등식이 성립하므로 $C$는 Monge Array입니다. 이걸로 분할정복 최적화를 적용할 수 있고 시간복잡도를 $O(GLlogL)$로 줄일 수 있습니다.

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

ll dp[805][8005];
ll C[8005];
ll pre[8005];
int L, G;

ll f(ll i, ll j) {
    return (i-j) * (pre[i]-pre[j]);
}

void solve(int lev, int s, int e, int optl, int optr) {
    if(s > e) return ;
    int mid = (s+e) >> 1;
    int opt = -1;
    ll &ans = dp[lev][mid];
    for(int i=optl;i<min(mid, optr);++i) {
        ll val = dp[lev-1][i] + (mid - i) * (pre[mid] - pre[i]);
        if(opt == -1 || ans > val) {
            opt = i; ans = val;
        }
    }
    solve(lev, s, mid-1, optl, opt+1);
    solve(lev, mid+1, e, opt, optr);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> L >> G;
    if(G >= L) G = L;
    for(int i=1;i<=L;++i) cin >> C[i];
    for(int i=1;i<=L;++i) pre[i] = pre[i-1] + C[i];
    for(int i=1;i<=L;++i) dp[1][i] = pre[i] * i;
    for(int i=2;i<=G;++i) solve(i, 1, L, 0, L);
    cout << dp[G][L] << '\n';
    return 0;
}