2개의 댓글이 있습니다.
-
-
WeissBlume -
동적계획법의 점화식이 구간트리나 우선순위큐의 도움을 받아 최적화될 수 있ㄱ습니다.
d(i): i번째에 불을 켰을 때 까지의 최소 비용.
d(i)=\min_{j\geq i−P}d(j)+cost(i)
여기서 cost(i)는 고정된 값이므로 d(j)의 최솟값만 빠르게 찾으면 바로 d(i)를 구할 수 있겠죠.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
cjkis
https://algospot.com/judge/problem/read/FIRE
동적계획법으로 하면 시간초과가 납니다..
구간트리나 우선순위큐로 풀면 된다고 하는데요
이건 최댓값이나 최솟값 구할 때 쓰는거 아닌가요?
그런데 최솟값만을 선택하면 답이 아니게 되는데염..
예를들어 |시작점| 1 3 2 3 |끝점|
에 시야가 3이라면
가장 적은돈만을 선택하면 1->2 이렇게 총비용이 3원인데요,
좀 비싸더라도 먼 2원을 선택하면 총 비용 2원으로 3원보다 더 저렴합니다.
즉, 시야내에 최솟값만을 선택한다면 답이 안되는데 어떻게 구간트리를 이용해서 답을 구할 수 있을깝쇼?
9년 전