테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Star Trek ======

===== 풀이 =====
  * [[ps:cht]]를 이용할수 있는 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])$ 형태의 [[ps:cht]]를 사용할수 있는 형태가 된다.
  * s[j]가 단조감소한다는 조건이 없으므로 [[ps:cht#직선이 정렬되지 않은 경우]]에 해당된다. 시간복잡도는 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
    * [[:ps:teflib:convexhulltrick#FullyDynamicChtWithQuerySet|teflib.convexhulltrick.FullyDynamicChtWithQuerySet]]
    * [[:ps:teflib:convexhulltrick#dp_with_cht|teflib.convexhulltrick.dp_with_cht]]

{{tag>BOJ ps:problems:boj:다이아몬드_5}}