Programação Competitiva

Dois jogadores, Alberto e Wanderley, disputam um jogo. Um conjunto com um número par de cartões contendo números inteiros é disposto sobre uma mesa, um ao lado do outro, formando uma sequência. Alberto começa, e pode pegar um dos dois cartões das pontas. Wanderley então pode pegar um dos dois cartões das pontas e novamente Alberto pode pegar um cartão das pontas, e assim por diante, até Wanderley pegar o último cartão.

Alberto, o primeiro a jogar, tem como objetivo maximizar o número total de pontos que ele consegue, somando os valores dos cartões escolhidos. Wanderley, o segundo jogador, quer atrapalhar o Alberto e fazer com que ele consiga o menor número de pontos possível. Em suma, ambos querem fazer o melhor possível, Alberto querendo maximizar sua soma e Wanderley querendo minimizar a soma de Alberto.

Você deve escrever um programa que, dada a sequência de cartões, determine o maior número de pontos que Alberto consegue obter.

Entrada

Cada caso de teste é descrito em duas linhas. A primeira linha contém um inteiro par N (2 ≤ N ≤ 10⁴), que indica o número de cartões sobre a mesa. A segunda contém N inteiros, que descrevem a sequência de cartões. Cada um dos N inteiros cabem em um inteiro de 32 bits.

Saída

Para cada caso de teste seu programa deve imprimir uma única linha, contendo um único inteiro, o maior número de pontos que Alberto consegue obter.

Exemplo

Entrada	Saída
4 0 -3 5 10 4 0 -3 5 7 4 47 50 -3 7	10 7 57

Solução em C/C++

_{* esta solução foi baseada na apresentada em https://www.life2coding.com/uri-online-judge-solution-1224-cards-intermediate-problem/}

#include <stdio.h>

int N, v[10000];
long long dp[10000][2];
 
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
 
int main() {   
    while (scanf("%d", &N) != EOF) {   
        for (int i = 0; i < N; ++i) {
            scanf("%d", &v[i]);
        }
        for (int i = 0; i < N - 1; ++i) {
            dp[i][0] = max(v[i], v[i + 1]);
        }
        int turn = 0;
        int pastTurn = 1;
        for (int intervalSize = 4; intervalSize <= N; intervalSize += 2) {
            pastTurn = turn;
            turn = (!(turn & 1));
            for (int i = 0, j = intervalSize - 1; j < N; ++i, ++j) {
                dp[i][turn] = max(v[i] + min(dp[i + 1][pastTurn], dp[i + 2][pastTurn]),
                                  v[j] + min(dp[i][pastTurn], dp[i + 1][pastTurn]));
            }
        }
        printf("%lld\n", dp[0][turn]);
    }
    return 0;
}

Teste o código em: https://ideone.com/IEmhOo