19949. Fechadura

Olá meus amigos nerds. Hoje vamos brincar de abrir fechaduras. Já que é isso que o problema 19949. Fechadura nos pede para fazer. Mais especificamente, dados uma serie de números (que representam a altura dos pinos da fechadura) e uma posição em que os pinos tem que ser colocados para que a fechadura se abra, determinar qual o número mínimo de movimentos de elevar ou abaixar os pinos para que a fechadura se abra.

Solução

Quando li esse problema pela primeira vez, achei que sua solução envolveria programação dinâmica, já que ele pedia o menor número de movimentos. Entretanto se observarmos bem, o problema afirma que quando um pino é mexido o da frente também o é. Assim, não há o que otimizar, basta percorrer o vetor com as alturas (armazenando o número de movimentos gastos para mover o pino anterior) e ir somando o número de movimentos necessários.

Seja 'altura' o vetor com as alturas dos pinos
Seja m a altura que devemos colocar os pinos
soma_mov = 0
acum = 0
for altura in alturas
        diff = m - (altura + acum)
        soma_mov += abs(diff)
        acum = diff

Implementação