..

헉 위키가 있었구나.. 감사합니다!

문제 풀면서 관찰했던 것들을 적어놨었네요. 이 3가지 정보로 풀었었습니다.

1. [i,j] 구간을 고려할 때 항상 [i,j]에 있는 모든 원소를 포함하는 것이 이득이다.

2. [i,j] 구간을 고려할 때 항상 마지막에는 i 또는 j 위치에 있는 것이 이득이다.

3. 편의상 1번째 점부터 n번째 점까지 순차적으로 방문하는 것이 최적이라 가정하고, i번째 점과 i+1번째 점 사이의 거리를 Di라 하면, 최적의 값은 sum( (n-k)*Dk ) 이다. (k : 1..n-1)