Solução Serrote

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.

https://gist.github.com/rogerioagjr/ebd55893e1a7f9788dd5ecbca817940d