sochun1518   3년 전

dp[K][0] := K 번 째 사건을 1번 경찰차가 해결했을 때, (1번 경찰차 위치, 2번 경찰차 위치, 최소cost )

dp[K][1] := K 번 재 사건을 2번 경찰차가 해결했을 때, (1번 경찰차 위치, 2번 경찰차 위치, 최소cost ) 로 정의를 했습니다...!


그리고 다음과 같이 점화식을 세웠습니다.

dp[K][0] := 그 전 사건까지 1번 경찰차가 해결한 최솟값 혹은 2번 경찰차가 해결한 최솟값 +  K 사건을 1번 경찰이 해결함으로써 추가로 발생되는 비용의 최솟값으로 정의했고, dp[K][1] 도 마찬가지입니다.

즉, 1번 사건부터 차례대로 1번 경찰과 2번 경찰들이 다 사건을 해결해나가며 기존의 사건을 해결한 상태에서 더 작은 값들을 저장해나가면서 dp 점화식을 채웠습니다. 현재 계속 틀렸습니다를 받는 상태고, 게시판의 반례는 다 돌려본 상태입니다 ㅠㅠ 구글링을 해보아도 다들 저랑 다르게 점화식을 잡으셔서 푸셨는데, 이 점화식이 어떤 케이스에서 틀리는지 알고 싶습니다.  

surung9898   3년 전

반례는 다음과 같습니다.

sochun1518   3년 전

너무 감사드립니다!!

이런 반례가 있었군요,,,,, 나름 혼자서 많이 테케 만들어봤는데 부족한 부분이 많았던 것 같습니다 감사합니다 :))

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