Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2285
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2285
Palíndrome
Por OBI - Olimpíada Brasileira de Informática 2004 
Brazil
Timelimit: 1
Uma cadeia de caracteres é chamada de palíndrome se seqüência de caracteres da esquerda para a direita é igual à seqüência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere, o segundo caractere seja igual ao penúltimo caractere, o terceiro caractere seja igual ao antepenúltimo caractere, e assim por diante). Por exemplo, as cadeias de caracteres ‘mim’, ‘axxa’ e ‘ananaganana’ são exemplos de palíndromes.
Se uma cadeia não é palíndrome, ela pode ser dividida em cadeias menores que são palíndromes. Por exemplo, a cadeia ‘aaxyx’ pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromes: {‘aa’, ‘xyx’}, {‘aa’, ‘x’, ‘y’, ‘x’}, {‘a’, ‘a’, ‘xyx’} e {‘a’, ‘a’, ‘x’, ‘y’, ‘x’}.
Escreva um programa que determine qual o menor número de partes em que uma cadeia deve ser dividida de forma que todas as partes sejam palíndromes.
Entrada
A entrada é constituída de vários conjuntos de teste. A primeira linha de um conjunto de testes contém um inteiro N (1 ≤ N ≤ 2000) que indica o número de caracteres da cadeia . A segunda linha contém a cadeia de caracteres, composta por letras minúsculas (de ‘a’ a ‘z’), sem espaços em branco. O final da entrada é indicado por N = 0.
Saída
Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter um inteiro indicando o menor número de partes que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromes. A terceira linha deve ser deixada em branco. O formato mostrado no exemplo de saída abaixo deve ser seguido rigorosamente.
| Exemplo de Entrada | Exemplo de Saída |
|
3 axa 6 xyzyyx 10 bbabcbbaab 0 |
Teste 1 1 Teste 2 4 Teste 3 4 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 2010
using namespace std;
int dp[MAXN], palindrome[MAXN][MAXN], tam, teste;
char entrada[MAXN];
int solve_palindrome(int ini, int fim) {
if (ini > fim) return 0;
if (palindrome[ini][fim] != -1) return palindrome[ini][fim];
if (ini == fim) {
return palindrome[ini][fim] = 1;
}
if (ini + 1 == fim) {
if (entrada[ini] == entrada[ini + 1]) return palindrome[ini][fim] = 1;
return palindrome[ini][fim] = 0;
}
if (entrada[ini] == entrada[fim] && solve_palindrome(ini + 1, fim - 1))
return palindrome[ini][fim] = 1;
return palindrome[ini][fim] = 0;
}
int main() {
while (scanf("%d", &tam) && tam) {
scanf("%s", entrada);
memset(palindrome, -1, sizeof(palindrome));
memset(dp, 0, sizeof(dp));
for (int i = tam; i >= 1; i--) {
entrada[i] = entrada[i - 1];
}
for (int i = 1; i < = tam; i++) {
dp[i] = MAXN;
for (int j = 0; j < tam; j++) {
if (solve_palindrome(j + 1, i)) {
dp[i] = min(dp[j] + solve_palindrome(j + 1, i), dp[i]);
}
}
}
printf("Teste %d\n%d\n\n", ++teste, dp[tam]);
}
return 0;
}
Input
axa
6
xyzyyx
10
bbabcbbaab
0
Output
1
Teste 2
4
Teste 3
4