블로그 이전

분류없음 2018.02.24 08:42

티스토리는 언제까지 서비스를 지속할지 불안정해서 ㅡㅡㅋ


https://nailbrainz.github.io

Posted by Nailbrainz

https://www.acmicpc.net/problem/1162


우선..다익스트라 한번 돌리고 k번 점프류 dp로 풀랬는데 틀림.


내 생각은 노드 n에서 k번째 포장을 사용해서 올 수 있는 최단거리 dp[k][n]은


dp[k-1][n]과 dp[k-1][주변노드]들의 최소값이라고 생각했는데, 이러면 멀리 있는 dp[k][엄청짧은노드]의 값이 propagation이 안됨.


결국 해결책은 다익스트라를 2차원 그래프에 대해([n][k]) 돌리는거였음. 이 2차원 다익스트라는 좀 재밌는듯.

당연하지만 2번의 inqueue과정이 있다. 하나는 기존 다익스트라 (k변화 없음)고, 나머지 하나는 k가 1 상승하는 inqueue. 


아그런데 생각해보니 k번 점프류 dp도 한번 bfs를 돌려주는데..그거 돌려줬으면 맞았을듯 ㅡㅡ;바보같이

어쨋건 이쪽이 구현이 훨 간편한 것 같다. 앞으로 k번 점프류 dp는 이 2차원 다익스트라로 풀어야지

'문제풀이 > 복습요망' 카테고리의 다른 글

도로포장  (0) 2018.02.23
RPG  (0) 2018.02.21
등차수열  (0) 2018.02.15
주유소  (0) 2018.01.03
Posted by Nailbrainz

RPG

문제풀이/복습요망 2018.02.21 22:54

https://www.acmicpc.net/problem/1315


DP문제인데 별로 dp같지 않다. 근데 러닝타임이 거의 1000*1000*100일텐데 0.5초밖에안되네?..


s, i가 일정할 시 결국 (어떻게 여기에 도달했든) 꺨 수 있는 퀘는 같다는 것이 중요. 이것만 보면 dp같네.

'문제풀이 > 복습요망' 카테고리의 다른 글

도로포장  (0) 2018.02.23
RPG  (0) 2018.02.21
등차수열  (0) 2018.02.15
주유소  (0) 2018.01.03
Posted by Nailbrainz