Serrote - Seletiva IOI 2016

serrote.cpp

// 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;
}