If we decide not to use card p, then the amount of owed cards decreases (unless it already is zero) and we move on to the next card. The damage performed is: f(p+1, max(0, owed - 1) ).
If we decide to use card p (There must be at least owed+level[p]-1 cards left). Then the amount of owed cards increases by level[p]. The total damage is : damage[p] + f(p+1, owed + level[p] - 1).
첫번째 선택하지 않는경우는 - 1을 하고 선택한경우는 저랑 정 반대로 됬군요..
어디서 논리의 오류가 발생했는지 잘 모르겠습니다. 조언 주시면 감사하겠습니다 !!
10년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
kws4679
탑코더 SRM 563 Hard 문제입니다.
간단히 요약하자면 카드가 N 개 있는데 각 카드별로
레벨이 있고 카드를 순서 상관하지 않고 뽑을수있는데
레벨 - 1 개의 카드가 오른쪽에 있어야 뽑을수있습니다.
그래서 DP 를 F(i, k) = i번째를 선택할때 i 번째 오른쪽에서
총 k 개를 선택했을때 최적해 라고 설계를 하고 관계식을 찾았습니다.
F(i, k) 에서
i + 1 번째부터 끝까지 중에 k 개를 선택해야 한다고 생각했습니다.
왜냐하면 i + 1 번째부터 끝까지중에 k 개를 선택해야 i 번째에서
선택하지 않더라도 총 선택한 카드의 개수가 k 개가 때문입니다.
중에 k - (level[i] - 1) 개를 선택해야 한다고 생각했습니다.
왜냐하면 i + 1 번째부터 끝까지중에 k - (level[i] - 1) 개를
선택하고 i 번째카드를 선택하면 level[i] - 1 개를 선택할수 없으
므로 선택한것과 마찬가지기 때문에 i, k 가 되기 때문입니다.
따라서 재귀 관계는
F(i, k) = 선택하지 않을경우 F(i + 1, k)
선택할경우 F(i + 1, k - (level[i] - 1))
그런데 http://apps.topcoder.com/wiki/display/tc/SRM+563
에 해설이 나와있는것을 보면 (변수는 저랑 똑같이 한것같습니다)
If we decide not to use card p, then the amount of owed cards decreases (unless it already is zero) and we move on to the next card. The damage performed is: f(p+1, max(0, owed - 1) ).
If we decide to use card p (There must be at least owed+level[p]-1 cards left). Then the amount of owed cards increases by level[p]. The total damage is : damage[p] + f(p+1, owed + level[p] - 1).
첫번째 선택하지 않는경우는 - 1을 하고 선택한경우는 저랑 정 반대로 됬군요..
어디서 논리의 오류가 발생했는지 잘 모르겠습니다. 조언 주시면 감사하겠습니다 !!
10년 전