Roteiro 12

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 11

Introdução

Um tema bastante recorrente em competições é o de Programação Dinâmica. Neste roteiro veremos técnicas um pouco mais avançadas do que as utilizadas no Roteiro 4. Veremos como identificar uma subestrutura ótima, definir uma equação de recorrência para o caso-base e para o enésimo termo, e então construir algoritmos que nos produzam a solução adequada. Além disso, veremos como reconstruir a solução ótima a partir dos dados computados pelo seu algoritmo.

Materiais de Apoio

Aqui apresentamos alguns materiais sobre Programação Dinâmica. Os três primeiros explicam o tema utilizando problemas classicos de PD, enquanto os dois últimos apresentam técnicas a serem usadas. É válido lembrar que existem ótimas explicações em materiais didáticos impressos.

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito esforço. Os problemas em rosa são de aquecimento. Não envolvem PD mas estimulam a criatividade, o que é muito bom para resolver os demais problemas.

Roteiro 12
# Problema Link Online Judge Nível
1 UVa 357 Let Me Count The Ways UVa 2
2 CAIXAS Desempilhando Caixas SPOJ-BR 2
3 MAÇAS Maçãs URI 2
4 PARQUE Parque Jurássico SPOJ-BR 2
5 ROBUSMG Melhorando a robustez de aplicações web SPOJ-BR 3
6 LCAIXA Livro-Caixa SPOJ-BR 4
7 NUVEMMG Computação em nuvem SPOJ-BR 3
8 CAMPSMS Campeonato de SMS SPOJ-BR 4
9 WCW Elementar, meu caro Watson! SPOJ-BR 2
10 UVa 12484 Cards UVa 3
11 CCODIGO Cadeado de Código SPOJ-BR 3

Próximo Roteiro

O próximo roteiro de treinamento tratará de problemas de Fluxo Máximo e Corte Mínimo em Teoria dos Grafos. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 2 em negrito.

Link para o Roteiro 13

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas