Solução por Pedro Racchetti
Contéudo utilizado:
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:
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
| #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]); | |
| } | |
| } | |