Solução Serrote

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Para ver o problema original, clique aqui. Esta foi uma das tarefas da Seletiva Brasileira para Olimpíada Internacional de Informática de 2016.

 

O problema é uma DP simples, basta encontrarmos a recursão. Vamos construir o serrote (n,k) a partir de outros serrotes de tamanho n-1, adicionando o número n (note que ele é maior que todos os outros números no serrote, logo sempre irá formar um dente se tiver vizinhos). Temos duas possibilidades: ou adicionamos o valor n em um serrote (n-1,k-1) de maneira a criar um novo dente ou inserimos em um serrote (n-1,k) de modo que nenhum novo dente seja criado.

Para não criarmos um novo dente, adicionamos o novo valor nas pontas ou dentro de algum dente já existente. Se a, b e c formam um dente, por exemplo, então adicionar um valor maior que os três entre a e b ou entre b e c não irá alterar a quantidade de dentes, pois iremos destruir o dente anterior para criar um novo. Em um serrote com k dentes há 2k lugares em quen podemos inserir um novo ponto dentro de um dente já existente, mais as duas pontas, logo há 2k+2=2(k+1) possibilidades para inserir um ponto sem alterar a quantidade dos dentes. Como há dp(n-1,k) maneiras de construir um serrote de n-1 pontos e k dentes, há dp(n-1,k) \times 2(k+1) maneiras de construir um serrote (n,k) a partir de um (n-1,k).

Vejamos agora como construir a partir de um serrote de tamanho n-1, com k-1 dentes, adicionando um ponto que cria um novo dente. Se há n maneiras de inserir um ponto em uma dada permutação (n-2 maneiras de inserir entre 2 dos n-1 pontos e 2 maneiras de inserir nas pontas) e sabemos que, com k-1 dentes, há 2((k-1)+1)=2k maneiras de inserirmos sem alterarmos a quantidade de dentes, então há n-2k maneiras de inserirmos de modo a aumentarmos a quantidade de dentes. Como há dp(n-1,k-1) maneiras de construir um serrote de n-1 pontos e k-1 dentes, há dp(n-1,k-1) \times (n-2k) maneiras de construir um serrote (n,k) a partir de um (n-1,k-1).

Somando as duas possibilidades de construção, temos que dp(n,k)=dp(n-1,k) \times 2(k+1) +dp(n-1,k-1) \times (n-2k). Basta agora escrevermos o caso base da recursão, que é bem simples. Para n=3, temos 4 maneiras de construir um serrote sem dentes (k=0), que são (1,2,3), (3,2,1), (3,1,2) e (2,1,3) e duas maneiras de construirmos um serrote com um dente (k=1), que são (1,3,2) e (2,3,1). Como estas são todas as permutações, então não há nenhuma maneira de construirmos um serrote de tamanho 3 com alguma outra quantidade de dentes (k \neq 0 e k \neq 1).

Basta implementarmos a função recursiva descrita acima, usando uma tabela de DP para evitarmos o recálculo. Segue o código para melhor entendimento.

 

 

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: