PKU 1651 - Multiplication Puzzle

Autor da análise: raphael_ribasraphael_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)
\begin{align} M(x, y) = \left\{ \begin{array}{ll} 0 & \textrm{se $x+1 = y$} \\ \textrm{min $\{ M(x, k) + M(k, y) + v_x v_k v_y | x < k < y \}$} & \textrm{se $ x+1 < y$} \end{array} \right \end{align}

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.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License