Solução de Rogério Júnior
Para ver o problema original, clique aqui.
Imagine um vetor de nome $$seq$$ em que aparecem todas as teclas que o competidor deve digitar, na ordem em que devem ser digitadas e repetidas exatamente o número de vezes que o competidor deve repetir. Imagine também que a matriz $$t[i][j]$$ tem guardado exatamente o tempo de mover um dedo da tecla de número $$i$$ para a de número $$j$$.
Resolver esse problema com uma $$DP$$ agora é bem simples. Seja o estado da DP definido pelas variáveis ($$esq$$, $$dir$$, $$pos$$), que significam as teclas em que estão os dedos direito e esquerdo e qual a posição em $$seq$$ da tecla que temos que apertar agora. Se a posição aponta para o fim de $$seq$$ (uma posição após a última), basta retornarmos zero. Caso contrário retornamos o melhor entre usar o dedo esquerdo ou o direito para pressionar a tecla em $$pos$$ mais $$0.2 s$$ que usamos para apertar a tecla. Seja $$prox$$ a tecla salva na posição $$pos$$ de $$seq$$. Seja $$total$$ a função recursiva que usaremos para calcular o valor de um estado da DP. Usar o dedo esquerdo tem custo $$t[esq][seq[pos]]$$ para movê-lo até a tecla e depois tem custo $$total(prox,dir,pos+1)$$ para terminarmos de digitar as teclas em $$seq$$, pois o dedo esquerdo agora está na tecla de número $$prox$$, o direito não se move e a próxima tecla a ser digitada é a que está na posição $$pos+1$$ de $$seq$$. De maneira análoga, usar o dedo direito tem custo $$t[dir][prox]+total(esq,prox,pos+1)$$.
Sabendo isso, basta calcularmos o valor da matriz $$t$$ e o vetor $$seq$$. Calcular $$t$$ é simples, basta salvarmos um vetor com $$11$$ posições em que a casa $$i$$ guarda um par de inteiros que representam as coordenadas do centro da tecla $$i$$ (podemos colocar o $$(0,0)$$ na tecla $$5$$, por exemplo) e usarmos dois $$for$$ para calcular a distância euclidiana entre quaisquer dois pontos do vetor e guardá-la em $$t$$.
Para criarmos o vetor $$seq$$, vamos ler cada caractere da entrada. Usando $$if$$ é fácil sabermos em qual tecla está o caractere a ser digitado e quantas vezes devemos apertar a tecla para que ele apareça. Se a tecla deste caractere for a mesma do anterior, devemos colocar a tecla $$10$$ em $$seq$$ antes da nova tecla. Feito isso, basta colocarmos a nova tecla em $$seq$$ quantas vezes for necessária.
Segue o código para melhor entendimento:
https://gist.github.com/rogerioagjr/65365d6a9e352433f899
Deixe um comentário