snrnsidy   3년 전

안녕하세요.

이 문제를 풀고 있는데 계속 시간초과에서 벗어나지 못하고 있습니다.

창고 i부터 창고 j까지 있는 물품을 i~j 사이에 있는 창고로 옮기는데 드는 최소 비용을 c[i][j]를 여러가지 방법으로 구하려고 하다가 삼분 탐색을 생각해서 구현을 했습니다.


예제는 맞는데 계속 시간초과가 나오네요. 혹시 c[i][j]를 n^2으로 구하는 다른 방법이 있는건가요? 도움을 주시면 정말 감사하겠습니다.
 

WeissBlume   3년 전

호옥시 C[i,j]를 최소로 만드는 위치를 A[i,j]라고 할 때, A[i,j] ≦ A[i,j+1]을 만족하지 않나요? 이 속성을 이용하면 전처리를 효율적으로 할 수 있을 것으로 보입니다!

snrnsidy   3년 전

답변 감사합니다.

답변을 읽어보니 어떻게 해야할지 감이 잡히네요. 감사합니다.

snrnsidy   3년 전


계속 질문을 달아서 죄송합니다. 최소 비용을 구할 때 저는 부분합으로 미리 계산을 하는데 여기서 overflow 문제가 발생해서 계속 시간초과가 나오는 듯 싶습니다. 혹시 __int128을 사용해야하거나 다른 방법을 사용해야 하는 건가요? 조언을 주시면 감사하겠습니다.

WeissBlume   3년 전

(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년 전

답변 정말로 감사합니다. 답변 보고 여러가지 해봤는데 시간초과의 벽을 넘을 수가 없네요ㅠㅠ 최적화를 할 때 루프 범위를 줄이라고 말씀하셨는데 어떻게 줄여야 할 지 감이 안잡히네요. 

snrnsidy   3년 전

도와주셔서 감사합니다ㅠㅠ 드디어 풀었습니다 감사합니다 

snrnsidy   3년 전

배열 참조할 때 오버헤드가 커서 시간초과가 나왔던 거 같습니다. 이걸 고치니깐 통과하네요

댓글을 작성하려면 로그인해야 합니다.