팬케이크 모으기 timer 30s memory 2048MB

앨리스와 밥은 둘 다 단 것을 좋아해서, 팬케이크를 모으는 게임을 하려고 한다. 탁자 위에는 \mathbf{N}개의 팬케이크 더미가 일렬로 놓여 있고, 1부터 \mathbf{N}까지 번호가 붙어 있다. i번째 더미에는 팬케이크가 정확히 \mathbf{A_i}개 있다. 앨리스와 밥은 번갈아 가며 턴을 진행하면서 더미 하나를 통째로 가져가는 방식으로 팬케이크를 모은다. 첫 턴에서 앨리스는 \mathbf{L_a}부터 \mathbf{R_a}까지(양 끝 포함) 번호가 붙은 더미 중 하나를 골라 가져가야 한다. 그 다음 밥은 \mathbf{L_b}부터 \mathbf{R_b}까지(양 끝 포함) 번호가 붙은 더미 중에서, 앨리스가 고른 것과는 다른 더미 하나를 골라 가져가야 한다.

이후의 턴에서는, 각자 이전에 자신이 가져간 더미와 인접한(옆에 붙어 있는) 아직 가져가지 않은 더미를 하나 골라야 한다. 즉 앨리스가 첫 턴 이후 어떤 턴에 더미 i를 가져가려면, 이전 턴들 중 하나에서 더미 i-1 또는 더미 i+1를 가져간 적이 있어야 한다. 밥도 마찬가지이다. 어느 시점에 한 플레이어에게 가능한 선택지가 없다면, 그 플레이어는 그 턴을 건너뛰며 아무 더미도 가져가지 않는다.

모든 더미가 가져가면 게임이 끝난다. 그때 앨리스는 자신이 가져간 모든 더미의 팬케이크를 전부 얻고, 밥도 자신이 가져간 모든 더미의 팬케이크를 전부 얻는다.

앨리스는 자신이 얻는 팬케이크의 수를 최대화하고 싶고, 밥도 자신이 얻는 팬케이크의 수를 최대화하고 싶다. 두 사람이 모두 최적으로 플레이할 때, 앨리스가 얻을 수 있는 팬케이크의 최대 개수를 구해 보자.