5개의 댓글이 있습니다.
-
-
deltaposter -
아닙니다 ㅠㅠ
답변 감사합니다 !!
9년 전 link
-
-
-
restart -
개수를 2^0..2^K꼴과 그 나머지로 쪼개서 0-1 Knapsack을 돌리는 방법도 있습니다. O(NVlgK).. 레퍼런스는 여기.. http://www.or.deis.unibo.it/kp/Chapter3.pdf
9년 전 link
-
-
-
deltaposter -
와....
다양한 방법이 있다는 길을 인도해주셔서 감사합니다!!
9년 전 link
-
-
-
WeissBlume -
저도 덕분에 드디어 책도둑을 풀 수 있겠네요 ㅋㅋㅋ
감사합니다!
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
deltaposter
문제
https://algospot.com/judge/problem/read/BOOKTHIEF
for (int i = 1; i <= n; ++i)
{
//여기서 PQ에 넣고 ?
}
머리가 미천한 나머지 아래 훌륭한 글들을 보고도 잘 모르겠습니다 ㅠ
https://algospot.com/wiki/read/Coders_high_2013
https://coders-high.wook.kr/solution/solution.pdf
아래 영역부터 어떻게 짜야할지 전혀 감이 안오는데
약간의 힌트라도.... 주시거나 아니면 이 문제에 대한 감을 얻기 위한 문제라도 추천해주시면 감사하겠습니다 !!
그렇다면 D[N][V]를 다음과 같이 구할수 있다.
f(V)값을 PQ에 넣는다.
PQ의 top인 x값이 V와 vi * ki를 넘게 차이나면 top을 제거한다
PQ의 top인 f(x)값에 대해 D[N][V] = f(x)+V/vi*ci이다.
최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NV lg V)이다.
이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다.
PQ안에 있는 2개의 t1 < t2에 대해 생각해보자.
만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다.
그러므로 이러한 t1은 전부 배제되었다고 가정하면,
PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
f(x1)≥f(x2)≥f(x3)≥...을 만족한다.
또한 위의 조건을 만족하도록 PQ를 관리하여야한다.
이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.
9년 전