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.
| // Serrote – Dia 1 – Seletiva IOI 2016 | |
| // Rogério Júnior | |
| // Complexidade: O(n*k) | |
| #include <cstdio> // scanf e printf | |
| #include <cstring> // memset | |
| #define MOD 1000000007LL // defino o valor de MOD | |
| #define MAXN 1010 // defino o valor de MAXN | |
| // defino que ll denominará o tipo long long | |
| typedef long long ll; | |
| // tabela de DP, para evitar recálculo | |
| ll dp[MAXN][MAXN]; | |
| // função recursiva que chama a DP Top-Down | |
| ll solve(ll n, ll k){ | |
| // se já tenho o resultado salvo, retorno o que tenho | |
| if(dp[n][k]>=0) return dp[n][k]; | |
| // caso base: se n=3 | |
| if(n==3){ | |
| // se k=0, há 4 possibilidades | |
| if(k==0) return dp[n][k]=4; | |
| // se k=1, há uma possibilidade | |
| if(k==1) return dp[n][k]=2; | |
| // para qualquer outro k, não há possibilidades | |
| return dp[n][k]=0; | |
| } | |
| // se n>3, então chame a recursão geral da DP, olhando como construir | |
| // o serrote de tamanho n a partir de serrotes de tamanho n-1 | |
| // e não podemos esquecer de retornar apenas o módulo (10^9+7) | |
| return dp[n][k]=(solve(n-1,k-1)*(n-2*k)+solve(n-1,k)*2*(k+1))%MOD; | |
| } | |
| int main(){ | |
| // marco todos os valores da DP como não calculados | |
| memset(dp,-1,nof dp); | |
| // declaro e leio os valores de n e k | |
| ll n, k; | |
| scanf("%lld %lld", &n, &k); | |
| // e imprimo a resposta para o n e o k fornecidos | |
| printf("%lld\n", solve(n,k)); | |
| return 0; | |
| } |

Comente