[일반] 오늘 D 머 어케 풀었음..?

[익명(222.109)]

해설 봐도 이해가 안대.. 살려줘..

[익명(skuld88)]

dp

[익명(222.109)]

ㅡㅡ

[익명(223.63)]

전형적인 게임 dp

[익명(222.109)]

돌게임은 좀 풀어보긴 했는데말야

[익명(223.63)]

앳코더 있는 educational dp contest에서 stones랑 deque 풀어봐라

[익명(222.109)]

오..

[mod998244353(dontbeaccused)]

지금까지 내가 이해한 식으론 dp(n) := 나 또는 너가 게임을 최적으로 하면서 n개의 돌을 취했을 때 내(혹은 너)가 가져가는 돌의 최댓값이라 두자. 그러면 각 반복마다 ai + ((n - ai) - dp[n - ai])의 최댓값을 찾으면 됨. n - ai는 당연하고 여기서 dp[n - ai]는 이전 턴에 상대가 달성한 최적해임. 그럼 반대로 내가 가져간 돌은 (n - ai) - dp[n - ai]개 라는 소리가 됨. dp 테이블을 왜 두 명한테 동일하게 적용할 수 있냐면 둘 다 최적으로 플레이를 하고 있는 상태이고 그러면 현재 반복에서 나는 비기거나 지고 있다는 소리임.

[mod998244353(dontbeaccused)]

첫 턴의 경우 0:0이니까 비기는거고 첫번째 플레이어가 아무거나 가져가면 두번째 플레이어는 당연히 지는 상태가 됨. 여기서 비기거나 지는 상황을 극복해야 하므로 현재 값이 최대가 되는 상태를 찾는 거으로 이해해봄 틀리면 고쳐줘 나도 배우고 싶음

[익명(118.235)]

100% 정확

[익명(222.109)]

오.. 고마워 정독할게

[익명(222.109)]

나는 dp테이블 두개 만들어서 두명을 따로 관리했었는데, 두명을 같은 테이블로 표현할 수 있다는게 머리에 안 꽂히네.. 여튼 고맙따

[익명(222.109)]

이해해버렸다..도움 많이 돼따..고맙따..