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 BR 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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
axa
6
xyzyyx
10
bbabcbbaab
0

Output

x
+
cmd
Teste 1
1

Teste 2
4

Teste 3
4
Advertisements

Demonstration


Previous
#2252 Beecrowd Online Judge Solution 2252 Discovering Password Solution in C, C++, Java, Js and Python
Next
#2286 Beecrowd Online Judge Solution 2286 Par ou Ímpar Solution in C, C++, Java, Js and Python