11584. Partitioning by Palindromes

 

We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, “racecar” is a palindrome, but “fastcar” is not.

A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (“race”, “car”) is a partition of  ”racecar” into two groups.

Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome?

For example: “racecar” is already a palindrome, therefore it can be partitioned into one group. “fastcar” does not contain any non-trivial palindromes, so it must be partitioned as (“f”, “a”, “s”, “t”, “c”, “a”, “r”).  “aaadbccb” can be partitioned as (“aaa”, “d”, “bccb”).

 

Input. Begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

 

Output. For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.

 

Пример входа

Пример выхода

3

racecar

fastcar

aaadbccb

1

7

3

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Пусть s – входная строка. Пусть f(i, j) содержит минимальное количество палиндромов, на которое можно разбить строку si…sj. Тогда ответом будет значение f(0, len – 1), где len – длина строки s. Значение f(i, j) будем запоминать в dp[i][j].

Если строка si…sj является палиндромом, то f(i, j) = 1.

Строка из одного символа всегда является палиндромом, так что f(i, i) = 1.

Иначе попробуем разбить строку si…sj на две: si…sk и sk+1…sj (i ≤ k < j). В этом случае

f(i, j) =

Получили алгоритм за O(n3), который дает TLE.

 

Реализуем рекурсивную функцию IsPal(i, j), которая возвращает 1, если si…sj является палиндромом. Иначе функция возвращает 0. Подстрока si…sj есть палиндром, если si = sj и si+1…sj-1 является палиндромом. Значения IsPal(i, j) запоминаем в ячейках pal[i][j].

В ячейках dp[j] будем вычислять наименьшее количество палиндромов, на которое можно разбить строку s1…sj. Положим dp[0] = 0 и dp[1] = 1 (строка из одной буквы является палиндромом). Значение dp[j] вычислим по формуле:

dp[j] =

Такое решение работает за O(n2) и проходит по времени.

 

Реализация алгоритма

 

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAX 1010

#define INF 0x3F3F3F3F

using namespace std;

 

int i, j, n;

char s[MAX];

int dp[MAX];

int pal[MAX][MAX];

 

int IsPal(int i, int j)

{

  if (i >= j) return pal[i][j] = 1;

  if (pal[i][j] != -1) return pal[i][j];

  return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);

}

 

int main(void)

{

  scanf("%d\n",&n);

  while (n-- > 0)

  {

    gets(s+1);

    memset(dp,0x3F,sizeof(dp));

    memset(pal,-1,sizeof(pal));

 

    dp[0] = 0; dp[1] = 1;

    for(j = 2; j <= strlen(s+1); j++)

      for(i = 1; i <= j; i++)

        if (IsPal(i,j)) dp[j] = min(dp[j], dp[i-1] + 1);

 

    printf("%d\n",dp[strlen(s+1)]);

  }

  return 0;

}

 

Реализация алгоритма – рекурсивная

 

#include <stdio.h>

#include <string.h>

#define MAX 1010

#define INF 0x3F3F3F3F

 

int n;

char s[MAX];

int dp[MAX][MAX];

int pal[MAX][MAX];

 

int IsPal(int i, int j)

{

  if (i >= j) return pal[i][j] = 1;

  if (pal[i][j] != -1) return pal[i][j];

  return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);

}

 

int solve(int i, int j)

{

  if (i == j) return dp[i][j] = 1;

  if (dp[i][j] != INF) return dp[i][j];

 

  if (IsPal(i,j)) return dp[i][j] = 1;

 

  for(int k = i; k < j; k++)

    if(IsPal(i,k))

    {

      int temp = 1 + solve(k+1,j);

      if (temp < dp[i][j]) dp[i][j] = temp;

    }

 

  return dp[i][j];

}

 

int main(void)

{

  scanf("%d\n",&n);

  while (n-- > 0)

  {

    gets(s);

    memset(dp,0x3F,sizeof(dp));

    memset(pal,-1,sizeof(pal));

    printf("%d\n",solve(0,strlen(s)-1));

  }

  return 0;

}

 

C++ TLE реализация O(n3)

 

#include <stdio.h>

#include <string.h>

#define MAX 1010

#define INF 0x3F3F3F3F

 

int n;

char s[MAX];

int dp[MAX][MAX];

 

int IsPal(int i, int j)

{

  while(i < j)

  {

    if (s[i] != s[j]) return 0;

    i++; j--;

  }

  return 1;

}

 

int solve(int i, int j)

{

  if (i == j) return dp[i][j] = 1;

  if (dp[i][j] != INF) return dp[i][j];

 

  if (IsPal(i,j)) return dp[i][j] = 1;

 

  for(int k = i; k < j; k++)

  {

    int temp = solve(i,k) + solve(k+1,j);

    if (temp < dp[i][j]) dp[i][j] = temp;

  }

  return dp[i][j];

}

 

int main(void)

{

  scanf("%d\n",&n);

  while (n-- > 0)

  {

    gets(s);

    memset(dp,0x3F,sizeof(dp));

    printf("%d\n",solve(0,strlen(s)-1));

  }

  return 0;

}