Programação Dinâmica - DP em intervalo

Aula por Caique Paiva

Conhecimento Prévio Necessário:

Programação Dinâmica

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):

Problema

(Link para Submeter).

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

[collapse]

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

(Link para Submeter)

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$ .

Solução

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).

[collapse]

Certo, vamos para outro problema antes de ir para o problema do começo da aula.

Problema Médio

(Link para submeter)

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$ .

Solução

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).

[collapse]

Certo, vamos para o problema do começo da aula agora!!

Problema Difícil

O enunciado está no começo da aula.

Solução

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)

[collapse]

Aula por Caique Paiva

Introdução

DP em Range

Problema Inicial

Problema Médio

Problema Difícil

Problemas Propostos