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.