BOJ 18049 Cheese Game

문제 링크:

문제 내용

$n$장의 카드가 일렬로 놓여 있습니다. 각 카드에 왼쪽부터 순서대로 양의 정수 $a_1, a_2, \cdots, a_n$이 쓰여 있습니다. 각 카드의 위치를 $1, 2, \cdots, n$이라고 합시다.

두 사람이 다음과 같은 게임을 합니다.

• 두 사람이 번갈아서 턴을 진행합니다.
• 자신의 턴인 사람은 원하는 만큼의 카드를 선택하여 모두 가져갈 수 있습니다. 이때, 어떤 두 선택된 카드의 위치가 1 차이가 나면 안됩니다. 한 사람이 카드를 가져간 뒤에도, 남아있는 카드의 위치는 유지됩니다.
• 각 사람의 목표는 자신이 가져간 모든 카드에 쓰인 수의 총합을 최대화하는 것입니다.

두 사람이 최선의 플레이를 할 때, 선공이 얻을 수 있는 카드의 값들의 합의 최댓값을 구하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 20$)

각 테스트 케이스에 대해, 첫 번째 줄에는 카드의 수 $n$이 주어집니다. ($1 \le n \le 100\;000$)

두 번째 줄에는 $a_1, a_2, \cdots, a_n$이 주어집니다. ($1 \le a_i \le 1\;000\;000$)

출력

각 테스트 케이스에 대해, 문제의 정답을 한 줄에 출력합니다.

문제 풀이