Quadrangle Inequality

1정의#

정수 인덱스 쌍 (i, j) (i ≤ j)에 대한 함수 w가 사각부등식(quadrangle inequality)을 만족한다는 것은, a ≤ b ≤ c ≤ d인 모든 정수 a, b, c, d에 대해 w(a, c) + w(b, d) ≤ w(a, d) + w(b, c)라는 것이다.

2최적 분할점의 단조성#

점화식 dp_j = min_{0 ≤ i < j} { dp_i + w(i, j) } (dp₀ = 0)을 정의한다. 각 j에 대해 최솟값을 달성하는 가장 작은 i를 opt_j라 한다.

이때 w가 사각부등식을 만족하면, 모든 j ≥ 1에 대해 opt_j ≤ opt_j+1이다.

3증명#

opt_j+1 = a < b = opt_j인 j가 존재한다고 가정한다.

b가 dp_j를 최소화하므로 dp_b + w(b, j) ≤ dp_a + w(a, j)이고, dp_a − dp_b ≥ w(b, j) − w(a, j).

a가 dp_j+1을 최소화하므로 dp_a − dp_b ≤ w(b, j+1) − w(a, j+1).

a ≤ b < j ≤ j+1이므로 사각부등식을 적용할 수 있다.

w(a, j) + w(b, j+1) ≤ w(a, j+1) + w(b, j)

즉, w(b, j) − w(a, j) ≥ w(b, j+1) − w(a, j+1)

모든 부등식을 연결하면 dp_a − dp_b ≤ w(b, j+1) − w(a, j+1) ≤ w(b, j) − w(a, j) ≤ dp_a − dp_b.

부등식의 양 끝이 같으므로 모든 부등호에서 등호가 성립한다. 특히 dp_b + w(b, j) = dp_a + w(a, j).

따라서 a도 dp_j를 최소화하므로 opt_j+1의 정의에 모순이다. ■