K. Security

ProblemK_Eng.pdf

$O(N^2)$ Dynamic Programming 으로 풀린다.

BOI 2009 beetle 문제와 매우 비슷한 문제이다. beetle 문제가 더 어렵고 이 문제는 더 간단하며, 다양한 풀이가 있을 것으로 예상된다.

우선 다이나믹 배열의 정의는 아래와 같다.

L[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_i$일 때 ($i < j$)

R[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_j$일 때 ($i < j$)

이 문제에서 N개의 점을 모두 방문해야한다. (i,j) 순서쌍이 있을 때 앞으로 몇 곳을 더 방문해야되는지 그 수를 계산할 수 있다. 앞으로 방문해야할 곳의 수를 $c$라 하자.

이후 거리 $d$를 이동해야되면 가중치로 $d$가 아닌, $c \times d$를 더한다.

점화식은 아래와 같다.

L[i][j] = min( L[i+1][j]+dist(i+1,i)*(N-j+i) , R[i+1][j]+dist(j,i)*(N-j+i) )

R[i][j] = min( L[i][j-1]+dist(i,j)*(N-j+i) , R[i][j-1]+dist(j-1,j)*(N-j+i) )

그리고 최종적으로 답은 min( L[1][N] , R[1][N] ) 이 된다.

K.cpp