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