segunda-feira, 9 de março de 2015

Maratona de Programação - Problema URI 1775

Olá pessoal, nesse post irei falar sobre um problema bem interessante que encontra-se disponível no URI Online Judge para quem quiser resolver.

Antes de visualizar as dicas, tente resolvê-lo:


O problema pede que você diga quantas paradas o André terá que fazer seguindo algumas regrinhas:

- Só pode remover as balas das pontas.

- Caso as balas forem iguais (as duas pontas iguais), então remove das duas pontas e só conta como uma parada.

- Se as pontas forem diferentes, então tem que escolher qual remover de forma a minimizar o número de vezes que ele irá parar para pegar as balas.

Para resolver você pode utilizar uma PD (programação dinâmica) onde cada estado é um subintervalo para ver se é melhor tirar da esquerda ou da direita.

Pode-se usar a estratégia bottom-up ou top-down, irei explicar utilizando a estratégia bottom-up.

Se temos "N" elementos, então declare uma matriz NxN, irei chamá-la de "pd".

Inicialize com 0 todos os elementos dessa matriz (pode utilizar "memset" do header string.h).

Inicialize os casos base de tamanho 1 com 1. Só fazer um "for" com o seguinte conteúdo:

pd[i][i] = 1

É inicializado com 1 porque só tem uma bala. Esse caso base são casos menores onde a partir deles iremos preencher a matriz.

pd[a][b] = min(pd[a][b-1] + 1, pd[a+1][b] + 1, pd[a+1][b-1] + 1)

"a" e "b" são subintervalos. Exemplo: a = 2 e b = 4 é um subintervalo do vetor de 2 à 4 e assim por diante.

O caso de "pd[a+1][b-1] + 1" só irá entrar caso "sabores[a] == sabores[b]". Esse vetor "sabores" é um vetor contendo a lista de sabores das balas que correspondem a números, o problema já fornece para você em cada caso de teste.

A resposta de cada caso de teste, após preencher a matriz, estará em pd[0][N-1]. Lembrando que tou indexando a partir do 0.

E mais, para você calcular corretamente, gere os pares (a,b) da seguinte forma:

(0, 1); (1, 2); (2, 3); (0, 2); (1, 3); (0, 3)

Isso eu fiz para 4 elementos (N = 4). Perceba que na forma (a,b), o "a" é sempre menor do que o "b". Se você não preencher dessa forma irá calcular errado, veja:

pd[2][1] =  min(pd[2][0] + 1, pd[3][1] + 1, pd[3][0] + 1)

Perceba que você quer calcular a pd[2][1], mas precisa da pd[3][1] e da pd[3][0] que você ainda não calculou. Portanto, preencha a matriz da forma que falei anteriormente.

Após preencher a matriz, a resposta estará em pd[0][N-1], basta imprimir isso, pois a pd[a][b] é o mínimo de paradas para comer todas as balas do subintervalo (a,b).

Essa solução passou com 1 segundo e pouco. Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: