Solução Cartões

0 Flares Facebook 0 0 Flares ×

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.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: