Эй! Это МОЯ рыба!

시간 제한2초메모리 제한1024 MB

요약

최대 10개의 빙판이 일렬로 놓인 판에서 두 명의 플레이어가 각자 펭귄 두 마리를 번갈아 배치하고 이동하며, 떠난 빙판을 가져가고, 첫 번째 플레이어가 강제할 수 있는 최대 점수 차를 구한다.

난이도: 보통10점 중 7점
유형: 게임 이론, 동적 계획법, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Одна из популярных настольных игр <<Эй! Это МОЯ рыба!>> состоит в перемещении пингвинов и сбору рыбы на поле.

Мы рассмотрим упрощенную версию этой игры. Для этой игры используется $n$ карточек с изображениями нескольких рыб и фишки-пингвины.

В начале игры карточки выкладываются на столе в ряд в некотором порядке.

Каждому игроку выдается по два пингвина. Затем первый игрок размещает одного из своих пингвинов на незанятой льдине. После этого второй игрок делает то же самое. После этого они аналогично размещают своих вторых пингвинов.

Как только все пингвины находятся на льдинах, лов рыбы начинается! Игроки ходят по очереди. Ход состоит из перемещения одного из пингвинов текущего игрока, после этого игрок берет льдину --- карточку, на которой его пингвин стоял в начале его хода, и кладет ее перед собой.

Пингвин может двигаться по льдинам любом направлении и остановиться на любой незанятой льдине. При этом запрещено перепрыгивать через других пингвинов и через проруби, оставшиеся после удаления льдин. Если у пингвина с обеих сторон препятствие, то он не может двигаться.

Если игрок не может переместить ни одного из его пингвинов, он забирает всех своих пингвинов и льдины, на которых эти пингвины стояли. После этого второй игрок продолжает делать ходы, пока он может перемещать своих пингвинов.

В конце игры каждый игрок считает количество рыб на всех собранных им карточках. Цель игрока максимизировать разность своего количества рыб и количества рыб противника. Какую максимальную разность может получить первый игрок, при оптимальной игре второго игрока.

입력

В первой строке входного файла число $n$ ( $4 \le n \le 10$ ) --- количество карточек. Во второй строке файла находится $n$ чисел $a\_i$ --- количество рыб на карточках в порядке в котором они выложены на столе. $1 \le a\_i \le 10^6$ .