DNC Opt / Monotone Queue Opt

1. 모든 $a \leq b$, $c \leq d$에 대해, $f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$가 성립한다면, $f(i, j)$는 사각 부등식 (Quadrangle Inequality), Monge Property를 만족한다.

$f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$를 다음과 같이 해석할 수 있다. 구간 $[a, d]$와 $[b, c]$를 선택하는 대신에 구간 $[a, c]$와 $[b, d]$를 선택하도록 바꿔주는 것이 이득이다.

 

2. $[l, r]$의 값들을 SUM한 함수와 MIN을 취한 함수는 Monge Property를 만족한다.

SUM 함수는 항상 $f(a, c)+f(b, d)=f(a, d)+f(b, c)$이니 성립한다.

MIN 함수는 전체 구간에 대한 minimum 값이 $[b, c]$에 있다면 $f(a, c)+f(b, d)=f(a, d)+f(b, c)$를 만족한다.

일반성을 잃지 않고 전체 구간에 대한 minimum 값이 $[a, b]$에 있다면 $f(a, c)$, $f(a, d)$는 이 minimum 값을 선택하고, 남은 $f(b, d)$, $f(b, c)$값 중 범위가 $f(b, d)$가 더 넓으니 $f(b, d) \leq f(b, c)$가 성립해, 준 식이 성립한다.

 

3. 각 $r$마다 $f(l, r)$이 최소인 값 중 가장 왼쪽인 $l$값을 $opt(r)$이라 한다면 $opt(r)$은 단조 증가한다.

단조 증가하지 않고, $p \leq q$이지만, $a=opt(p) \geq b=opt(q)$인 $p, q$가 존재한다 가정하자.

opt의 정의에 따라 $f(a, p) \leq f(b, p)$, $f(a, q) \geq f(b, q)$가 성립한다.

두 식을 더하면 $f(a, p)+f(b, q) \leq f(b, p)+f(a, q)$이고, 이는 Monge Property에 모순이다.

즉, $a \leq b$이고, $opt(r)$은 단조 증가 함수이다.

 

4. 1사분면에 단조 감소하는 점들의 집합 P와, 3사분면에 단조 감소하는 점들의 집합 Q가 있을 때, P의 점 하나와 Q의 점 하나를 이용하여 만들 수 있는 직사각형의 넓이를 $f(i, j)$이라 할 때, $f(i, j)$는 Monge Property를 만족한다. (ICPC WF Money For Nothing)

 

5. $dp(i, k)=min_{j<i}{dp(j, k-1)+f(j, i)}$로 정의될 때 각 $i$마다 $dp(i, k)$를 최소로 하는 값 중 가장 왼쪽인 $j$값을 $opt(i)$이라 한다면 $opt(i)$는 단조 증가한다.

증명 과정은 위 3과 동일하다.

 

6. 5번 성질을 이용하여 Divide & Conquer을 이용하면 문제를 $O(NKlogN)$에 해결할 수 있다.

$solve(l1, r1, l2, r2)$은 $[l1, r1]$의 모든 $dp(i, k)$값을 구하는 함수이다. $[l1, r1]$의 opt값의 후보가 되는 구간이 $[l2, r2]$이니, 가운데 값인 mid1의 opt를 구한 후, 이를 이용하여 $solve(l1, mid1-1, l2, mid2)$, $solve(mid1+1, r1, mid2, r2)$를 구해주면 된다.

 

7. $p \leq q$, $i \leq j$일 때, $dp(p)+f(p, i) \geq dp(q)+f(q, i)$라면 $dp(p)+f(p, j) \geq dp(q)+f(q, j)$이다.

$p \leq q$, $i \leq j$일 때, $dp(p)+f(p, j) \leq dp(q)+f(q, j)$라면 $dp(p)+f(p, i) \leq dp(q)+f(q, i)$이다.

$dp(p)+f(p, i) \geq dp(q)+f(q, i)$이고, $dp(p)+f(p, j) \leq dp(q)+f(q, j)$라 가정하자.

두 식을 더하면 $f(p, i)+f(q, j) \geq f(q, i)+f(p, j)$이고, 이는 Monge Property에 모순이다.

위 성질을 이용하여 특정 $x$를 기준으로 $i \leq x$에 대해, $dp(p)+f(p, i) \leq dp(q)+f(q, i)$, 즉 $p$가 더 최적이며, $i > x$에 대해, $dp(p)+f(p, i) \geq dp(q)+f(q, i)$, 즉 $q$가 더 최적이다.

$p$, $q$에 대해서만 본다면 $g_p(x)=dp(p)+f(p, x)$라 정의했을 때, $g_p(x)$는 일차함수와 비슷한 성질을 가짐을 의미한다.

 

8. 7번 성질을 이용하여 $dp(i)=min_{j<i}{dp(j)+f(j, i)}$를 $O(NlogN)$에 해결할 수 있다.

두 함수 $p \leq q$ $g_p(x)$, $g_q(x)$에 대해, 두 함수의 대소관계가 갈리는 특정 $x$를 $cross(p, q)$라 하자.

$cross(p, q)$를 구하는 과정은 단순한 이분탐색을 통해 $O(logN)$에 계산해줄 수 있다.

스택에 $p \leq q \leq r$이라면 $cross(p, q) \leq cross(q, r)$이 성립하도록 스택에 함수들을 뒤에서부터 삽입한다.

이 과정은 일차함수들을 스택에 관리하는 CHT와 동일하다.

이후 앞에서부터 더이상 opt의 범위를 벗어난 일차함수들을 제거해주는 과정을 거치면, 가장 앞쪽의 함수가 최적의 함수이다.

전체 과정은 Deque를 이용하여 $O(NlogN)$에 관리할 수 있다.

 

9. 7번 성질을 이용하여 $g_p(x)$를 단순 일차함수로 취급하여 일반적인 CHT나, Li Chao Tree 등의 자료구조를 응용하여 활용할 수 있다.