사용자 도구

사이트 도구


ps:problems:boj:17526

Star Trek

ps
링크acmicpc.net/…
출처BOJ
문제 번호17526
문제명Star Trek
레벨다이아몬드 5
분류

DP, CHT

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어PyPy
제출기록169976KB / 476ms
최고기록476ms
해결날짜2023/01/26

풀이

  • 볼록 껍질을 이용한 최적화를 이용할수 있는 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 정도에 통과

코드

토론

댓글을 입력하세요:
B C O G T
 
ps/problems/boj/17526.txt · 마지막으로 수정됨: 2023/01/26 03:36 저자 teferi