|
|
Problema H - Lego Mosaics |
Autor: Pedro Ribeiro (Faculdade de Ciências da Universidade do Porto)
Tipo de problema: Programação Dinâmica
Gerar realmente todas as maneiras possíveis de fazer o mosaico não passa no tempo. Tal como é dito no problema A, quando é necessário optimizar algo (máximos/mínimos) ou contar algo, e onde a solução "bruta" é exponencial, podemos muitas vezes usar programação dinâmica (PD).
No caso deste problema, a primeira coisa a notar é que linhas diferentes são independentes. E que sequências de cores diferentes na mesma linha, ou da mesma cor mas separadas por espaços vazios, são também independentes. Considere o seguinte caso do exemplo de input:
.... YYBB YBBB ....
Seja ways[i] o número de maneiras de criar um segmento horizontal da mesma cor de tamanho i. Então, o número de maneiras total para o exemplo é igual a ways[2]*ways[2]*ways[1]*ways[3], pois todos estes segmentos são independentes (os dois da linha de cima de tamanho 2, e os dois da linha de baixo de tamanhos 1 e 3).
Dito isto, resta conseguir calcular ways[i]. Se considerarmos a última peça a colocar, podemos fazer o seguinte: colocar uma peça de tamanho 1, e fica o resto do segmento de tamanho i-1 por preencher; colocar uma peça de tamanho 2, e fica o resto do segmento de tamanho i-2 por preencher, e por aí adiante.
De um modo mais formal:
ways[i] = ways[i-1] + ways[i-2] + ways[i-3] + ways[i-4] + ways[i-6] + ways[i-8] + ways[i-10] + ways[i-12]
Este fórmula pode ser usada directamente se considerarmos que para i<0, ways[i]=0 e que o caso base seria ways[0]=1.
Tal como no caso do problema A, podemos preencher ways[i] de trás para a frente (bottom-up), começando pelos tamanhos mais pequenos, ou calculando à medida que for necessário, usando memoization.
Ligações interessantes: