Nome: Zak Galou
Link: http://br.spoj.pl/problems/ZAK/
Dificuldade: 9/10
Linguagem: C++
Tempo atingido: 1.40
Memória usada: 22M
Colocação alcançada: 89
Tentativas: 10
Comentário:
Ta aí um exercício "combo" dos últimos exercícios que resolvi.
O exercício Zak Galou explora o 'problema da mochila' (knapsack) e a BFS (Busca em Amplitude).
É usado o problema da mochila para descobrir a quantidade de mana necessária para matar o monstro. Nesse caso o dano seria o o valor, e a mana o peso.
Após descoberto o custo para se chegar a cada sala, é só aplicar uma BFS. Recomendo o algoritmo do Dijkstra.
Dicas:
- Estudem o "problema da mochila" (knapsack problem). Recomendo atenção ao método por programação dinâmica.
- Estudem um algoritmo para fazer um BFS. Recomendo o Dijkstra.
- O valor resultante pode chegar na casa do bilhão.
Nenhum comentário:
Postar um comentário