Divide & Conquer Optimization in DP

동적계획법에서의 분할정복 최적화 기법에 대해서 글을 써보려고 한다.

일반적으로 j<i일 때, D(k, i) = min(D(k-1, j) + W(j, i))에서 W 함수가 quadrangle inequality를 만족할 때 사용할 수 있다. quadrangle inequality은 정수 a,b,c,d가 a<b<c<d일 때, W(a, d) + W(b, c)와 W(a, c) + W(b, d)가 항상 한쪽 방향으로 부등식이 성립하는 조건을 얘기한다. 부등식이 성립하면 다음과 같은 사실이 성립된다.

D(k, i) = min(D(k-1, j) + W(j, i))에서 최솟값이 될 때의 j 값을 C(k, i)라 하자.

p<q에 대해 W(a,d) + W(b, c) > W(a, c) + W(b, d)이면 C(i, p)≤C(i, q)이고, W(a,d) + W(b, c) < W(a, c) + W(b, d)이면 C(i, p)≥C(i, q)이다.

증명은 comet님의 블로그를 참고하면 되겠다.

따라서 D(k, i)를 계산했고, C(k, i) = p이면

1) D(k, a) (a < i)를 구할 때는 j≤p에 대해서만 D(k-1, j) + W(j, a)를 참조하면 되고

2) D(k, b) (i < b)를 구할 때는 j≥p에 대해서만 D(k-1, j) + W(j, b)를 참조하면 된다.

각 k의 i에 대해 divide & conquer를 하면 divide depth는 (log N)이 되고, D(k, i)를 계산하는데 참조하는 D(k-1)에 대해서 O(N)이므로 O(KN log N)이 된다.

연습문제로 BOJ 11001 김치 문제가 있다.

이 문제에서 구하고자 하는 것은 1≤i≤j≤N일 때, max(T(i)*(i-j)+V(j))이다. W(j, i) = T(i)*(i-j)+V(j)라 하면 W(a, d) + W(b, c) - W(a, c) - W(b, d) =  T(d)(b-a) + T(c)(a-b) = (b-a)(T(d)-T(c))가 되고, T(i)≥T(i+1)이라서 항상 음수가 됨을 알 수 있다. 따라서 D(i) = max(T(i)*(i-j)+V(j))라 두고, C(i)를 이용해 다음과 같은 코드를 작성할 수 있다.

#include <stdio.h>
#define MN 100005
#define max(a, b) ((a)>(b)?(a):(b))
#define min(a, b) ((a)>(b)?(b):(a))
typedef long long ll;
int N, D, opt[MN];
ll T[MN], V[MN], answer;
void f(int L1, int R1, int S1, int E1) {
    if (L1 > R1 || S1 > E1) return;
    int M = (L1 + R1) / 2;
    ll res = 0;
    for (int i = max(S1, M - D); i <= min(M, E1); i++) if (T[M] * (M - i) + V[i] > res) res = T[M] * (M - i) + V[i], opt[M] = i;
    if (answer < res) answer = res;
    f(L1, M - 1, S1, opt[M]);
    f(M + 1, R1, opt[M], E1);
}
int main() {
    scanf("%d%d", &N, &D);
    for (int i = 1; i <= N; i++) scanf("%lld", &T[i]);
    for (int i = 1; i <= N; i++) scanf("%lld", &V[i]);
    f(1, N, 1, N);
    printf("%lld", answer);
}