divide & conquar optimization

D[t][i] = min (D[t-1][j] + C[j][i]) (j < i) 꼴인 경우 

위의 조건을 만족하는 최소의 j를 P[t][i]라고 할때 

P[t][i] <= P[t][i+1] < --- > C[a][c] + C[b][d] <= C[a][d] + C[b][c] 증명은 귀류법!

반대로 

D[t][i] = max (D[t-1][j] + C[j][i]) (j < i) 꼴인 경우 

위의 조건을 만족하는 최소의 j를 P[t][i]라고 할때 

P[t][i] <= P[t][i+1] < --- > C[a][c] + C[b][d] >= C[a][d] + C[b][c] 증명은 귀류법!

위의 조건을 이용해 divide & conquar 방식으로 로그시간만에 dp table 값을 계산 할 수 있다.

증명

(1)

C[a][c] + C[b][d] <= C[a][d] + C[b][c]

D[t][i] = min( D[t-1][k] + C[k][i] )

A[t][i] <= A[t][i+1]

귀류법

어떤 i에 대해서 

A[t][i] = j > A[t][i+1] = k

D[t][i] = D[t-1][j] + C[j][i] < D[t-1][k] + C[k][i]

D[t][i+1] = D[t-1][k] + C[k][i+1] < D[t-1][j] + C[j][i+1]

D[t-1][j] - D[t-1][k]에 대해 정리해보면

C[k][i+1] - C[j][i+1] < D[t-1][j] - D[t-1][k] < C[k][i] - C[j][i]

즉 C[k][i+1] - C[j][i+1] < C[k][i] - C[j][i]

다시써서 C[k][i+1] + C[j][i] < C[k][i] + C[j][i+1] 에서 (k < j < i < i+1)

사각 부등식을 만족한다는 가정에 모순되므로 위 명제는 참이다

(2)

C[a][c] + C[b][d] >= C[a][d] + C[b][c]

D[t][i] = max( D[t-1][k] + C[k][i] )

A[t][i] <= A[t][i+1]

귀류법

어떤 i에 대해서

A[t][i] = j > A[t][i+1] = k

D[t][i] = D[t-1][j] + C[j][i] > D[t-1][k] + C[k][i]

D[t][i+1] = D[t-1][k] + C[k][i+1] > D[t-1][j] + C[j][i+1]

D[t-1][j] - D[t-1][k]에 대해 정리해보면

C[k][i] - C[j][i] < D[t-1][j] - D[t-1][k] < C[k][i+1] - C[j][i+1]

즉 C[k][i] - C[j][i] < C[k][i+1] - C[j][i+1] 

다시 써서 C[k][i] + C[j][i+1] < C[k][i+1] + C[j][i] 에서 (k < j < i < i+1)

사각 부등식을 만족한다는 가정에 모순되므로 위 명제는 참이다

boj 김치 문제

D[i] = i날에 꺼낼때 max value

D[i] = (i-j+1) * T[i] + V[j] ( j < i)로 정의되므로 

C[j][i] = (i-j+1) * T[i] + V[j]가 된다

사각 부등식의 조건을 살펴 보면

C[a][c] + C[b][d] - C[a][d] - C[b][c] 

= (c-a+1) * T[c] + V[a] + (d-b+1) * T[d] + V[b] - (d-a+1) * T[d] - V[a] - (c-b+1) * T[c] - V[b]

= (c-a+1-c+b-1) * T[c] + (d-b+1-d+a-1) * T[d]

= (b-a) * T[c] + (a-b) * T[d]

= (b-a) (T[c] - T[d]) 로 정리되며

a<b<c<d , T[a] > T[b] > T[c] > T[d]라는 조건에서

준 식의 값은 양수가 된다 

즉 다시써서 C[a][c] + C[b][d] > C[a][d] + C[b][c] 를 만족하므로 divide & conquar optimization 을 사용 할 수 있다