Solução Informática - Nível Intermediário - Semana 5

Solução por Pedro Racchetti

Contéudo utilizado:

Programação Dinâmica

Para esse problema, podemos ver que é possível calcular a resposta recursivamente, já que quando testarmos a pressão em valor $x$ e $k$ telefones, pode-se-ter dois casos:

o telefone dobra, tendo então que usar $k - 1$ telefones, na pressão $x - 1$ ;
O telefone não dobra, tendo então que usar o mesmo número de telefones, para pressões $x + 1$ até $m$ , com $k$ telefones

Perceba que o segundo caso, é equivalente a testar no intervalo de $1$ até $m - x$ . A recursão $f(x, k)$ portanto é a seguinte, sendo $k$ o número de telefones e $x$ a pressão atual:

$f(x, 1) = x$ , já que com um telefone é necessário usar todas as pressões abaixo, no pior caso;
$f(0, k) = 0$ , já que com pressão $0$ nenhum telefone irá quebrar;
$f(1, k) = 1$ já que basta apenas testar em $1$ para pressão $1$
$f(x, k) = min(max(f(i - 1, k - 1), f(x - i, k)) + 1)$ para todo $i$ no intervalo $[ 1, x [$ .

Porém, se apenas usarmos uma função recursiva, a complexidade ficará exponencial, não passando devido a tempo. Para corrigir isso, podemos usar programação dinâmica para armazenar os valores já calculados. Note também que não podemos calcular todos os valores em cada caso de teste, obrigando o cálculo da programação dinâmica a ser feito antes do processamento dos casos de testes.

Segue o código para melhor compreensão:

	#include<bits/stdc++.h>
	using namespace std;

	const int maxp = 55, maxm = 1010;
	const int INF = 1e9 + 7;

	int dp[maxm][maxp]; //Matriz que irá guardar os valores da programação dinâmica


	int main(){
	//inicializamos a DP com "infinito" para todos os valores
	for(int i = 1; i <= maxp; i++){
	for(int j = 0; j <= maxm; j++){
	dp[j][i] = INF;
	}
	}
	//montamos a base da DP
	for(int i = 0; i <= maxm; i++) dp[i][1] = i;
	for(int i = 1; i <= maxp; i++) dp[1][i] = 1, dp[0][i] = 0;

	//calculamos os valores da DP, antes dos casos de teste
	for(int k = 2; k <= maxp; k++){
	for(int x = 2; x <= maxm; x++){
	for(int i = 1; i < x; i++){
	dp[x][k] = min(dp[x][k], max(dp[i - 1][k - 1], dp[x - i][k]) + 1);
	}
	}
	}

	int t;
	int cont = 0; //contador para o caso de teste

	scanf("%d", &t);
	while(t--){
	int n, m;
	scanf("%d %d", &n, &m);
	printf("Case %d: %d\n", ++cont, dp[m][n]);

	}


	}

view raw

testededobra.cpp

hosted with ❤ by GitHub