• 볼록 껍질을 이용한 최적화를 이용할수 있는 DP 문제이다.
• DP[i] 를 i번 행성(0-based) 까지 도착하데 걸리는 최소시간이라고 하고 점화식을 세우자.
  • $DP[0] = 0 $
  • $DP[i] = min_{j<i}(DP[j] + p[j] + s[j]\cdot dist(j,i))$
  • 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 정도에 통과

(다이아몬드 이상은 코드 생략)

• Dependency
  • teflib.convexhulltrick.FullyDynamicChtWithQuerySet
  • teflib.convexhulltrick.dp_with_cht