Autor da análise: raphael_ribas
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1651
Resumo
É dado uma sequência de cartas que são colcadas uma ao lado da outra, cada carta possui um número. O jogo consiste em retirar uma carta de cada vez, com exceção das cartas das extremidades. A pontuação de cada carta retirada é o produto do número da carta e dos números das cartas imediatamente a direita e a esquerda que ainda não foram retiradas. O objetivo do jogo é obter a menor pontuação possível.
Solução
O problema pode ser resolvido com uma programação dinâmica, basta observarmos que se escolhermos uma carta para ser a última a ser retirada, a solução da subsequência a direita dessa carta não depende da solução da subsequência da esquerda, e vice versa.
Então seja $v_i$ o número da $i$-ésima carta, então a melhor solução para a subsequência que inicia na $x$-ésima carta de termina na $y$-ésima carta é dado por:
(1)A solução que estamos procurando é $M(1, N)$, dado que $N$ é o número total de cartas na mesa.
Essa recorrência pode ser computada em tempo $O(N^3)$ porque é gasto um tempo $O(N)$ para testar todas as possíveis cartas que podem ser a última, e existem $O(N^2)$ subsequências.
Discuta o problema