Solução Cartões

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Para resolvermos o problema, usaremos uma DP bem simples: Seja $dp[ini][fim]$ a maior quantidade de pontos que Alberto consegue obter quando a parte da sequência que eles têm disponível é a compreendida entre os cartões de índices $ini$ e $fim$ na sequência original.

Deste modo, a DP é bem simples: se $ini>fim$, não há movimento possível, logo podemos obter pontos e devemos retornar $0$. Caso contrário, ainda há movimentos possíveis (com no mínimo dois cartões, pois quando Alberto joga, o número de cartões é sempre par), logo, devemos olhar qual cartão Alberto devia tirar: o da ponta esquerda ou da ponta direita.

Supondo que os cartões estão salvos no $array$ de nome $vetor$. Se ele remover o cartão da esquerda, ele ganhará os pontos deste cartão ($vetor[esq]$) mais o que ele ganhará com o resto da sequência, que agora está compreendida entre $ini+1$ e $fim$. Note que Wanderley irá jogar de modo a minimizar os pontos de Alberto, logo, veremos em qual das condições Alberto pontua menos (Wanderley tirando o cartão da esquerda ou da direita) e a retornaremos. Deste modo, se Alberto retirar o cartão da esquerda, ganhará $vetor[ini]+min(dp[ini+2][fim], dp[ini+1][fim-1])$. De maneira análoga, se ele retirar o da direita, ganhará $vetor[fim]+min(tab[ini+1][fim-1], tab[ini][fim-2])$. Basta retornarmos a melhor das escolhas.

O único problema com este código é a memória, que excede o limite do juiz se submetermos uma matriz de tamanho $10^4 \times 10^4$, para ser nossa tabela de DP. Para contornar isso, usaremos o seguinte truque: usaremos uma DP bottom-up e só vamos guardar na matriz os estados que realmente precisamos para calcular os novos estados. Para calcularmos uma coluna da matriz, só precisamos das duas colunas anteriores, pois para calcularmos um estado cuja última carta é $fim$, só precisamos dos cálculos com os estados com $fim-1$ e $fim-2$ (observe a regra da recursão). Assim, nossa matriz só terá 3 colunas, e usaremos colunas já utilizadas, escrevendo por cima delas, quando se tornarem inúteis, para economizar memória. Quando formos calcular a coluna $3$, as colunas $1$ e $2$ estarão lá para o cálculo, mas a escreveremos por cima da coluna $0$. Quando calcularmos a coluna $4$, onde precisaríamos da $3$ e $2$, usaremos a $0$ e $2$, ou seja, vamos olhar apenas para o resto de $fim$ módulo $3$.

No fim, basta retornarmos o valor de $dp[1][fim \ mod \ 3]$. Segue o código para melhor entendimento. Note que, nele, o nome da tabela de DP é $tab$.