Aula por Caique Paiva
Conhecimento Prévio Necessário:
Introdução
O objetivo da aula vai ser apresentar a ideia de DP em intervalo (range DP, em inglês) e resolver o seguinte problema (Leia o artigo antes de pensar nele):
[spoiler title=’Problema ‘ style=’green’ collapse_link=’true’]
Você tem uma string de tamanho $$n$$. Também temos $$q$$ perguntas para responder, que são descritas por dois inteiros $$l_i, r_i (1 \le l_i \le r_i \le n)$$. A resposta é a quantidade de palíndromos no intervalo $$[l_i, r_i]$$ da string.
Uma string é dita palíndroma se ela é lida da mesma maneira da esquerda para direita. Por exemplo $$aabbaa$$ é palindromo, mas $$aab$$ não é.
Input
A primeira linha tem uma string $$s$$ ($$1 \le |s| \le 5000$$). A segunda linha contém um inteiro $$q$$ ($$1 \le q \le 10^6$$), o número de perguntas. As próximas $$q$$ linhas contém as perguntas. A $$i$$-ésima linha contém dois inteiros $$l, r$$, a descrição da $$i$$-ésima pergunta.
Imprima $$q$$ inteiros, as respostas das perguntas.
Exemplo
| Entrada | Saída |
caaaba 5 1 1 1 4 2 3 4 6 4 5 |
1 7 3 4 2 |
[/spoiler]
DP em Range
Imagine um problema que temos um vetor $$v$$, e queremos responder perguntas de intervalos $$[l, r]$$ desse vetor. Além disso, temos a seguinte propiedade
- Conseguimos calcular a resposta da pergunta do intervalo $$[l, r]$$ com as respostas dos intervalos $$[l, u]$$ e $$[u+1, r]$$, com $$u$$ variando de $$l$$ até $$r-1$$.
Então, a ideia é fazer uma $$dp$$ nisso! Os estados da $$dp$$ seriam dois valores $$dp(l, r)$$, que significa a resposta para a pergunta do intervalo $$[l, r]$$. Para fazermos uma $$dp$$, precisamos de 3 coisas:
- Caso base: Normalmente o caso de intervalos $$[l, l]$$, ou seja, com só um valor no intervalo, são fáceis e podem ser feitos na mão, ou seja, temos como os casos bases as $$dp(l, l)$$.
- Transição: Para calcular $$dp(x, y)$$, como dito acima, usamos os valores de $$dp(x, u)$$ e $$dp(u+1, y)$$.
- Resposta final: Retornamos $$dp(l, r)$$, que é a resposta da pergunta.
Como é só uma ideia abstrata, podemos adaptar algumas dessas ideias para cada problema, como vocês vão ver abaixo. Além disso, temos um total de $$O(n^2)$$ intervalos em um vetor $$v$$ de tamanho $$n$$, e também, na transição nós usamos $$O(n)$$ valores para calcular $$dp(x, y)$$, então, normalmente uma dp em range roda em $$O(n^3)$$.
Problema Inicial
Dado um retângulo $$a \times b$$, sua tarefa é corta-lo em quadradros. Em cada movimento, você pode selecionar um retângulo e corta-lo em dois retângulos de modo que os lados continuam inteiros. Qual é o mínimo número possível de movimentos?
Limites
$$N \le 500$$
Input
O input tem dois inteiros $$a$$ e $$b$$.
Output
Imprima a menor quantidade possível de movimentos
| Entrada | Saída |
3 5 |
3 |
Nota
A solução seria:
As operações seriam: dividir o $$3 \times 5$$ por um $$3 \times 3$$ e $$2 \times 3$$, e então dividir o $$2 \times 3$$ em $$2 \times 2$$ e $$2 \times 1$$, e para finalizar dividir o $$2 \times 1$$ em $$1 \times 1$$ e $$1 \times 1$$.
[spoiler title=’Solução’ style=’yellow’ collapse_link=’true’]
Vamos fazer $$dp(x, y)$$ para ser a quantidade de operações para resolver o problema para um retângulo $$x \times y$$.
Caso base: $$dp(x, x) = 0$$, pois ele já é um quadrado
A transição vai ser
$$dp(x, y) = min(min_{1 \le k < x}(dp(k, y) + dp(x-k, y) + 1, min_{1 \le k < y}(dp(x, k) + dp(x, y-k) + 1))$$
Isso é verdade pois estamos simulando construir uma linha que divida o retângulo em dois. Ou seja, se temos o retângulo de lados $$[x, y]$$ e vamos dividir esse retângulo por uma reta que corta o lado de tamanho $$x$$ em $$t$$ e $$x-t$$, então basta resolvermos o problema para o retângulo $$[t, y]$$ da maneira mais rápida possivel, e o outro retângulo que sobra é o $$[x-t, y]$$, que também temos que resolver da maneira mais rápida possivel, então, nesse caso, gastamos $$dp(t, y) + dp(x-t, y) + 1$$ operações. Testando todas as divisões possíveis que nós conseguimos fazer, chegaremos na resposta mínima!
Veja que essa solução roda em $$O(N^3)$$ (temos $$N^2$$ dp para calcular e cada dp tem uma transição de $$O(N)$$). Segue o código para melhor entendimento (Link).
[/spoiler]
Certo, vamos para outro problema antes de ir para o problema do começo da aula.
Problema Médio
Lobo adora jogar jogos no seu celular. Ele está bem animado com o seguinte jogo:
Tem uma sequência de $$N$$ inteiros positivos, com todos eles entre ($$1$$ e $$40$$). Lobo pode pegar dois números consecutivos com valores iguais e trocar eles por um único número com o valor uma unidade maior (Por exemplo, ele pode pegar dois números 7 e trocar por um 8). O objetivo é maximizar o valor do maior número no final do jogo.
Dado uma configuração inicial do jogo, diga qual é o maior número que o lobo consegue alcançar.
Limites:
$$2 \le N \le 248$$
Input
A primeira linha do input tem $$N$$, e as próximas $$N$$ linhas dá a sequência de $$N$$ números do começo do jogo.
Output
Ache o maior inteiro que o Lobo consegue gerar.
| Entrada | Saída |
4 1 1 1 2 |
3 |
Nota
Nesse exemplo, o Lobo pode juntar o segundo e o terceiro $$1$$ para obter a sequência $$1 2 2$$, e então juntar os dois $$2$$ em um $$3$$.
[spoiler title=’Solução’ style=’blue’ collapse_link=’true’]
Vamos definir a $$dp(x, y)$$ da seguinte forma:
$$dp(x, y) = -1$$ Se não consegumos transformar todos os números em só um no intervalo $$[x, y]$$.
$$dp(x, y) = t$$ Caso contrário, onde $$t$$ é o maior número que consegumos gerar.
Então, os casos bases seriam $$dp(i, i) = v[i]$$ onde $$v$$ é a sequência de números que o problema dá. Portanto, o algoritmo para calcular $$dp(l, r)$$ seria
Começe inicializando $$dp(l, r) = -1$$., e então repita o seguinte algoritmo, começando com $$t =l$$ e indo até $$r-1$$.
Se $$dp(l, t) = dp(t+1, r)$$ e dp $$dp(l, t) \neq -1$$, isso significa que conseguimos transformar $$[l, t]$$ em um número só, $$[t+1, r]$$ também, e eles são o mesmo número! Ou seja, fazendo as operações, conseguimos transformar $$[l, r]$$ em $$dp(l,t) + 1$$, basta transformar $$[l, t]$$ em $$dp(l, t)$$, fazer a mesma coisa para $$[t+1, r]$$, e juntar os dois. Logo, a resposta de $$dp(l, r) = \max (dp(l, r), dp(l, t) + 1)$$.
(Detalhe: Veja que, se em nenhum momento conseguimos transformar $$[l, r]$$ em um cara só, $$dp(l, r) = -1$$, pois não entramos na condição do algoritimo em nenhum momento, e nós inicializamos $$dp(l, r) = -1$$).
Então, no final, retornamos o maior valor que está na matriz $$dp[N][N]$$. Esse algoritmo roda em $$O(N^3)$$ (Temos $$O(N^2)$$ intervalos para calcular e, para cada intervalo, fazemos $$O(N)$$ operações para calcular ele). Segue o código para melhor entendimento (Link).
[/spoiler]
Certo, vamos para o problema do começo da aula agora!!
Problema Difícil
O enunciado está no começo da aula.
[spoiler title=’Solução’ style=’orange’ collapse_link=’true’]
Seja $$dp(l, r)$$ a quantidade de palíndromos no intervalo $$[l, r]$$, além disso, seja $$pal(l , r)$$ uma função que retorna 1 se o intervalo $$[l, r]$$ é palíndromo, e 0 caso contrário. Também vamos fazer $$pal(l, r)$$ como uma dp. Primeiro, vamos calcular $$pal(l, r)$$.
Veja que $$pal(i, i) = 1$$, pois é só uma letra, então lida da esquerda para direita continua a mesma coisa. Agora, se no intervalo $$[l, r]$$, se $$s[l] \neq s[r]$$, então $$[l, r]$$ não é um palíndromo. Agora, se $$s[l] = s[r]$$, basta ver agora se $$[l+1, r-1]$$ é um palíndromo, que está calculado em $$pal(l+1, r-1)$$, então, a fórmula fica da seguinte maneira.
$$pal(l, r) = (s[l] == s[r] ? pal(l+1, r-1) : 0)$$
Perfeito!! Agora com pal calculado, vamos calcular a $$dp$$. Primeiro, veja que se um palindromo está no intervalo $$[l+1, r]$$, então ele está em $$[l, r]$$, além disso, se um palíndromo está em $$[l, r-1]$$, então ele está em $$[l, r]$$. Agora, os palíndromos se são contados duas vezes em $$[l+1, r]$$ e em $$[l, r-1]$$ são os que estão em $$[l+1, r]$$ e em $$[l, r-1]$$ ao mesmo tempo, ou seja, os que estão em $$[l+1, r-1]$$. Agora, a única subsequência que não foi contada foi a que não está em $$[l+1, r]$$ e em $$[l, r-1]$$, ou seja, o intervalo $$[l, r]$$. Portanto, a resposta de $$dp(l, r)$$ vai ser
$$dp(l, r) = dp(l+1, r) + dp(l, r-1) – dp(l+1, r-1) + pal(l, r)$$
Que são todos os palíndromos em $$[l+1, r]$$, em $$[l, r-1]$$, porém nós contamos os palíndromos de $$[l+1, r-1]$$ duas vezes, portanto temos que tirar eles uma vez para eles serem contados só uma vez!! (Essa ideia se chama de princípio da inclusão-exclusão). E então, caso $$(l, r)$$ for um palíndromo, colocamos ele também.
Esse código roda em $$O(N^2)$$ (Temos $$O(N^2)$$ dp para calcular, e cada uma leva $$O(1)$$ operações para ser calculada). Segue o código para melhor entendimento (Link)
[/spoiler]