호옥시 C[i,j]를 최소로 만드는 위치를 A[i,j]라고 할 때, A[i,j] ≦ A[i,j+1]을 만족하지 않나요? 이 속성을 이용하면 전처리를 효율적으로 할 수 있을 것으로 보입니다!
14179번 - 크리스마스 이브
호옥시 C[i,j]를 최소로 만드는 위치를 A[i,j]라고 할 때, A[i,j] ≦ A[i,j+1]을 만족하지 않나요? 이 속성을 이용하면 전처리를 효율적으로 할 수 있을 것으로 보입니다!
(1) (거리의 최댓값) * (무게의 최댓값) * (N의 최댓값) ≤ 1e6 * 1e6 * 5e3 < 1e18 이므로 long long 으로도 overflow는 일어나지 않을 것 같아요
(2) https://www.acmicpc.net/source... 를 보았을 때 dp 테이블을 채우는 부분을 최적화 할 여지가 많이 보입니다. 이를테면 dp[2][5001]을 사용한다거나(locality), (1..m)을 채울 때 dp[t][m+1...]은 볼 필요가 없으니 루프 범위를 좀 더 줄인다거나..
댓글을 작성하려면 로그인해야 합니다.
snrnsidy 3년 전 1
안녕하세요.
이 문제를 풀고 있는데 계속 시간초과에서 벗어나지 못하고 있습니다.
창고 i부터 창고 j까지 있는 물품을 i~j 사이에 있는 창고로 옮기는데 드는 최소 비용을 c[i][j]를 여러가지 방법으로 구하려고 하다가 삼분 탐색을 생각해서 구현을 했습니다.
예제는 맞는데 계속 시간초과가 나오네요. 혹시 c[i][j]를 n^2으로 구하는 다른 방법이 있는건가요? 도움을 주시면 정말 감사하겠습니다.