Palíndromo

palindromo.cpp

#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;
}