Solução por Rogério Júnior
Para ver o problema original, clique aqui.
O problema é uma DP em que o valor de refere-se ao melhor palíndromo encontrado entre os índices e (inclusive) da inicial. Cada estado da DP retorna dois inteiros: (número de caracteres especiais) e (tamanho do palíndromo). Seja a fornecida na entrada.
Se , então o palíndromo terá tamanho 1, e só terá um caractere especial se for uma das posições especiais. Se , então, se as letras forem iguais temos um palíndromo de tamanho 2 e basta contarmos os caracteres especiais (no caso ou ) 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 , então podemos usar ou não as letras e no nosso palíndromo resposta. Se usarmos adicionamos 2 ao tamanho de e o número de novos caracteres especiais (verificamos e e adicionamos 1 para cada um que seja especial). Se não as usarmos, vemos o melhor entre usar a letra esquerda () ou a direita ().
Se , 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |