티스토리 뷰

ICPC/2013 인터넷예선

K. Security

전명우 2013.09.29 20:26


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



'ICPC > 2013 인터넷예선' 카테고리의 다른 글

데이터 만들기  (0) 2013.09.30
K. Security  (1) 2013.09.29
I. Pickup Game  (2) 2013.09.29
H. Networks with Unidirectional Links  (2) 2013.09.29
G. Moore Machine  (0) 2013.09.29
F. KCPC  (0) 2013.09.29
댓글
  • 프로필사진 hongjun7 대회 때는 시작점이 정해져있으니까 생각하기 편하게 메모이제이션으로 짰었는데... 이 코드가 훨씬 깔끔하네ㅋㅋㅋ 2013.09.30 13:45 신고
댓글쓰기 폼