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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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