Розбиття на паліндроми#11245

Розбиття на паліндроми (Розбір)

Нехай $s$ — вхідний рядок. Підрядок $s_{i} ... s_{j}$ s_i~...~s_j є паліндромом, якщо виконується одна з наступних умов:

$i \geq j$ i \ge j (підрядок порожній або складається з одного символу);
$s_{i} = s_{j}$ s_i = s_j і підрядок $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} є паліндромом;

Нехай функція $I s P a l (i, j)$ IsPal(i, j) повертає $1$ , якщо $s_{i} ... s_{j}$ s_i ... s_j є паліндромом, і $0$ в іншому випадку. Значення $I s P a l (i, j)$ IsPal(i, j) зберігаємо в комірках $p a l [i] [j]$ pal[i][j].

Нехай функція $f (i, j)$ f(i, j) повертає мінімальну кількість розрізів, необхідних для паліндромного розбиття рядка $s_{i} ... s_{j}$ s_i~...~s_j. Значення цієї функції будемо зберігати в комірках масиву $d p [i] [j]$ dp[i][j]. Тоді відповіддю на задачу буде значення $f (0, s . s i z e () - 1)$ f(0, s.size() - 1).

Зазначимо, що $f (i, i) = 0$ f(i, i) = 0, тому що рядок з однієї букви вже є паліндромом.

Для обчислення $f (i, j)$ f(i, j) розділимо підрядок $s_{i} ... s_{j}$ s_i~...~s_j на дві частини: $s_{i} ... s_{k}$ s_i~...~s_k і $s_{k + 1} ... s_{j} (i \leq k < j)$ s_{k+1}~...~s_j~(i \le k < j). Рекурсивно розв'язуємо задачі на рядках $s_{i} ... s_{k}$ s_i~...~s_k і $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. Шукаємо таке значення $k (i \leq k < j)$ k~(i \le k < j), для якого сума $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1 буде мінімальною. Доданок $1$ в сумі означає, що ми робимо один розріз між символами $s_{k}$ s_k та $s_{k + 1}$ s_{k+1}. Таким чином, отримуємо наступне рекурентне співвідношення:

f (i, j) = i \leq k < j min (f (i, k) + f (k + 1, j) + 1)

f(i, j) = \min_{i \le k < j} (f(i,k) + f(k + 1, j) + 1)

Приклад

Наприклад, для рядка " $abab cc b$ " з $7$ символів маємо:

f (1, 7) = 1 \leq k < 7 min (f (1, k) + f (k + 1, 7) + 1)

f(1, 7) = \min_{1 \le k < 7} (f(1,k) + f(k + 1, 7) + 1)

Сума набуває найменшого значення при $k = 3$ k = 3:

f (1, 7) = f (1, 3) + f (4, 7) + 1 = 0 + 0 + 1 = 1

f(1, 7) = f(1, 3) + f(4, 7) + 1 = 0 + 0 + 1 = 1

Оскільки рядки " $aba$ " і " $b cc b$ " є паліндромами, то $f (1, 3) = f (4, 7) = 0$ f(1, 3) = f(4, 7) = 0.

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

Оголосимо константи, вхідний рядок $s$ та робочі масиви.

#define MAX 1001
#define INF 0x3F3F3F3F
int dp[MAX][MAX], pal[MAX][MAX];
string s;

Функція $I s P a l (i, j)$ IsPal(i, j) перевіряє, чи є підрядок $s_{i} ... s_{j}$ s_i~...~s_j паліндромом. Підрядок $s_{i} ... s_{j}$ s_i~...~s_j є паліндромом, якщо $s_{i} = s_{j}$ s_i = s_j і $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} є паліндромом. Значення $I s P a l (i, j)$ IsPal(i, j) зберігаємо в комірках масиву $p a l [i] [j]$ pal[i][j].

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

Функція $f (i, j)$ f(i, j) повертає мінімальну кількість розрізів, необхідних для паліндромного розбиття підрядка $s_{i} ... s_{j}$ s_i~...~s_j.

int f(int i, int j)
{

Якщо $i = j$ i = j, підрядок $s_{i} ... s_{j}$ s_i~...~s_j складається з одного символу, і розрізати її немає сенсу. Якщо $i > j$ i > j, підрядок $s_{i} ... s_{j}$ s_i~...~s_j вважається порожнім, і розрізи також не потрібні.

  if (i >= j) return 0;

Якщо значення $f (i, j)$ f(i, j) вже було обчислено раніше, повертаємо збережене значення з масиву $d p [i] [j]$ dp[i][j].

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

Якщо підрядок $s_{i} ... s_{j} (i < j)$ s_i~...~s_j~(i < j) є паліндромом, то розрізати її немає сенсу. В цьому випадку мінімальна кількість розрізів дорівнює $0$ .

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

Розділимо підрядок $s_{i} ... s_{j}$ s_i~...~s_j на дві частини: $s_{i} ... s_{k} (i \leq k)$ s_i~...~s_k~(i \le k) і $s_{k + 1} ... s_{j} (k + 1 \leq j)$ s_{k+1}~...~s_j~(k + 1 \le j). Далі рекурсивно розв'язуємо задачі для обох частин: $s_{i} ... s_{k}$ s_i~...~s_k і $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. Шукаємо таке значення $k (i \leq k < j)$ k~(i \le k < j), для якого сума $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1 найменша.

  for (int k = i; k < j; k++)
    dp[i][j] = min(dp[i][j], f(i, k) + f(k + 1, j) + 1);

Повертаємо відповідь $d p [i] [j] = f (i, j)$ dp[i][j] = f(i, j).

  return dp[i][j];
}

Основна частина програми. Читаємо вхідний рядок.

cin >> s;

Ініціалізуємо масиви.

memset(dp, 0x3F, sizeof(dp));
memset(pal, -1, sizeof(pal));

Обчислюємо і виводимо відповідь.

res = f(0, s.size() - 1);
cout << res << endl;