BOJ 5466 상인 (IOI 2009 Salesman)

https://www.acmicpc.net/problem/5466

5466번: 상인

문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제

• 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합.
• DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기.

위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면,

우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 방문하고 얻을 수 있는 최대 이익이라고 하면,

DP[i] = max (j < i)

• DP[j] - (L[i] - L[j]) * D + M[i] (when L[i] > L[j], 강물을 따라 내려감)
• DP[j] - (L[j] - L[i]) * U + M[i] (when L[i] < L[j], 강물을 거슬로 올라감)

강물을 따라 내려가는 경우의 식을 조금만 더 전개를 해보면, 아래의 식을 유도할 수 있다.

max (j < i) { DP[j] - (L[i] - L[j]) * D + M[i] }
= max (j < i) { DP[j] + L[i] * D - L[j] * D + M[i] }
= max (j < i) { DP[j] + L[j] * D} - L[i] * D + M[i] (j에 대해 상수항을 max절 밖으로)

어떤 j에 대해서 f(j) = max (j < i) { DP[j] + L[j] * D } 를 효과적으로 찾을 수 있다면 문제를 풀 수 있는 실마리가 보인다. 이미 알고 있는 자료구조 중 segment tree를 통해서 O(log n) 시간에 쿼리를 수행할 수 있다. 

i 보다 먼저 방문한 시장들 중에서 이득을 최대로 만들 수 있는 시장을 세그먼트 트리에서 쿼리를 한다. 이때 쿼리의 결과 값은 DP[j]가 아니라 DP[j] + L[j] * D 가 최대가 되는 값을 얻기를 원한다. 따라서 DP[i]를 구하고 나서 세그먼트 트리를 업데이트할 때, DP[i] + L[i] * D 값을 이용해서 업데이트를 해야 한다.

강물을 거슬로 올라가는 경우에 대해서도 별도의 세그먼트 트리를 이용하여 값을 관리하면 된다.

 

이 문제의 두 번째 난관은, 시장들이 같은 날에 열릴 수 있다는 것이다.

여러 시장이 같은 날에 열리는 경우 그리디 전략을 취할 수 있다.

같은날에 열리는 시장을 위에서부터 순서대로 a, b, c, d, e라고 하자.

우선, 강물을 따라 내려가는(다운스트림) 경우를 생각해보자.
a를 방문하고 b를 방문을 하는 것과, b를 방문하는 것을 비교를 해봐서 더 이득이 되는 쪽을 선택한다.
다시 b를 방문을 하고 (a를 방문하고 b를 방문했든지, b를 바로 방문했든지 간에) c를 방문하는 것과, c를 바로 방문하는 것을 비교를 해서 더 이득이 되는 쪽을 택한다. 이것이 c를 다운스트림을 따라 방문을 하는 방법 중 최적의 방법이 된다. (a를 방문하고 b를 건너뛰고 c를 방문하는 것보다. a를 방문을 했다면 b도 방문하고 c를 방문하는 것이 무조건 이득이기 때문. 또한 a->c->b나 c->a->b 처럼 시장을 건너뛰어서 방문하는 경우는 이동거리에 손해를 보게 되므로 이득이 될 수 없다. 다음날에  b와 가까운 시장 p에 방문하고 싶은 경우라도, a->c->b->p로 가는것 보다 a->b->c->p로 가는것이 손해볼 일이 없다.)
이를 마지막 시장까지 반복한다. 

강물을 거슬러 올라가는(업스트림) 경우도 비슷하게 할 수 있다.

교휸

* DP 점화식이 j < i 에 대해서 max나 min을 찾아야 하고, j에 관한 항과 i에 관한 항이 분리가 되면 세그먼트 트리를 이용하여 O(log n)에 DP항 하나를 채울 수 있다.