Solução Palíndromo

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

 

O problema é uma DP em que o valor de dp(ini,fim)refere-se ao melhor palíndromo encontrado entre os índices ini e fim (inclusive) da string inicial. Cada estado da DP retorna dois inteiros: qtd (número de caracteres especiais) e tam (tamanho do palíndromo). Seja word a string fornecida na entrada.

Se ini=fim, então o palíndromo terá tamanho 1, e só terá um caractere especial se ini for uma das posições especiais. Se ini==fim-1, então, se as letras forem iguais temos um palíndromo de tamanho 2 e basta contarmos os caracteres especiais (no caso ini ou fim) e, caso sejam diferente, o maior palíndromo tem tamanho 1 (uma das duas) e vai ter 1 caractere especial se uma das letras for especial.

Se word[ini]=word[fim], então podemos usar ou não as letras word[ini] e word[fim] no nosso palíndromo resposta. Se usarmos adicionamos 2 ao tamanho de dp[ini+1][fim=1] e o número de novos caracteres especiais (verificamos word[ini] e word[fim] e adicionamos 1 para cada um que seja especial). Se não as usarmos, vemos o melhor entre usar a letra esquerda (dp[ini][fim-1]) ou a direita (dp[ini+1][fim]).

Se word[ini] \neq word[fim], então não podemos usar as duas letras e voltamos para a segunda opção do caso anterior. Segue o código par melhor entendimento:


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 2200
#define MAXC 30
#define F first
#define S second
int n, tam, especial[MAXN];
char word[MAXN];
// struct que guarda o tipo que a DP retorna
struct subpal{
// ele tem dois inteiros
int qtd, tam;
subpal(int qtd_=0, int tam_=0){ qtd=qtd_; tam=tam_; }
// e operadores +, < e > para facilitar a implementação da DP
subpal operator +(const subpal x) const{ return subpal(qtd+x.qtd, tam+x.tam); }
bool operator >(const subpal x) const{ if(qtd!=x.qtd) return qtd>x.qtd; return tam>x.tam; }
bool operator <(const subpal x) const{ if(qtd!=x.qtd) return qtd<x.qtd; return tam<x.tam; }
};
// tabela de DP
subpal dp[MAXN][MAXN];
// DP recursiva
subpal palindr(int ini, int fim){
// se já tiver calculado o caso, retorno o valor na tabela
if(dp[ini][fim]>subpal(-1,-1)) return dp[ini][fim];
// se ini==fim, uso word[ini] como meu palíndromo
if(ini==fim) return dp[ini][fim]=subpal(especial[fim], 1);
// se o intervalo tiver apenas duas letras checo se posso usar as duas (se forem iguais)
// caso contrário, uso apenas uma
if(ini==fim-1){
if(word[ini]==word[fim]) return dp[ini][fim]=subpal(especial[ini]+especial[fim],2);
else return dp[ini][fim]=subpal(max(especial[ini],especial[fim]),1);
}
// se as letras forem iguais, checo o melhor entre usar as duas ou apenas uma delas
if(word[ini]==word[fim]){
subpal usa=palindr(ini+1,fim-1)+subpal(especial[ini]+especial[fim], 2);
subpal nao_usa=max(palindr(ini,fim-1), palindr(ini+1,fim));
return dp[ini][fim]=max(usa, nao_usa);
}
// se não forem, olho qual das letras devo preservar
else return dp[ini][fim]=max(palindr(ini,fim-1), palindr(ini+1,fim));
}
int main(){
// defino todos os estados da DP como não visitados
for(int i=0; i<MAXN; i++)
for(int j=0; j<MAXN; j++)
dp[i][j]=subpal(-1,-1);
// leio a entrada
scanf(" %s %d", word, &n);
tam=strlen(word);
for(int i=1; i<=n; i++){
int p;
scanf("%d", &p);
especial[p-1]=1;
}
// imprimo a resposta, que será DP(0,tam-1)
printf("%d\n", palindr(0, tam-1).tam);
return 0;
}

view raw

palindromo.cpp

hosted with ❤ by GitHub