dist(j,i)는 j번째 행성에서 i번째 행성까지의 거리인데, 이것은 0번 행성부터 i번 행성까지의 거리를 distsum에 구해두면 (단순 누적합), dist(j,i) = distsum[i] - distsum[j]이 된다.
그러면 위의 식은
$DP[i] = min_{j<i}(DP[j] + p[j] + s[j]\cdot (dist_psum[i] - distsum[j]))$ 이 되고
이걸 다시 정리하면 $DP[i] = min_{j<i}(s[j] \cdot distsum[i] + DP[j] + p[j] - s[j] \cdot distsum[j])$ 형태의 볼록 껍질을 이용한 최적화를 사용할수 있는 형태가 된다.
s[j]가 단조감소한다는 조건이 없으므로 직선이 정렬되지 않은 경우에 해당된다. 시간복잡도는 O(nlogn).
처음에는 더 느린 우주선으로 갈아타는 것은 말이 안되므로, s를 단조감소하는 순서로 남겨두고 나머지는 지워버려도 될것이라고 생각했다. WA를 맞고 나서도 이유를 떠올리는데 한참 걸렸다 ㅜㅜ.. s0=10, s1=1, s2=5 인 경우일때, s1에서 s2로 갈아탈일은 전혀 없지만, p값에 따라서는 s0에서 s1을 안갈아타고 바로 s2로 갈아타는게 득일수 있다. 따라서 s2를 지우면 안된다..
n이 100,000 밖에 안되는데도, python에서는 제한시간 1초 안에 통과하지 못한다. pypy로 440ms 정도에 통과