Palindromları bölmək#11245

Palindromları bölmək (Həll təhlili)

Tutaq ki, $s$ — giriş sətiridir. Alt sətir $s_{i} ... s_{j}$ s_i~...~s_j palindromdur, əgər aşağıdakı şərtlərdən biri yerinə yetirilirsə:

$i \geq j$ i \ge j (alt sətir ya boşdur, ya da bir simvoldan ibarətdir);
$s_{i} = s_{j}$ s_i = s_j və alt sətir $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} palindromdur;

$I s P a l (i, j)$ IsPal(i, j) funksiyası $s_{i} ... s_{j}$ s_i ... s_j palindromdursa $1$ , əks halda $0$ qaytarır. Bu funksiyanın dəyərlərini $p a l [i] [j]$ pal[i][j] hüceyrələrində saxlayırıq.

Tutaq ki, $f (i, j)$ f(i, j) funksiyası sətir $s_{i} ... s_{j}$ s_i~...~s_j-nin palindrom bölməsinə görə lazım olan minimal kəsim sayını qaytarır. Bu funksiyanın dəyərlərini $d p [i] [j]$ dp[i][j] massivinin hüceyrələrində saxlayacağıq. Onda məsələnin cavabı $f (0, s . s i z e () - 1)$ f(0, s.size() - 1) dəyəri olacaq.

Qeyd edək ki, $f (i, i) = 0$ f(i, i) = 0, çünki bir hərfdən ibarət sətir artıq palindromdur.

$f (i, j)$ f(i, j)-i hesablamaq üçün alt sətir $s_{i} ... s_{j}$ s_i~...~s_j-ni iki hissəyə bölək: $s_{i} ... s_{k}$ s_i~...~s_k və $s_{k + 1} ... s_{j} (i \leq k < j)$ s_{k+1}~...~s_j~(i \le k < j). Rekursiv olaraq $s_{i} ... s_{k}$ s_i~...~s_k və $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j sətirləri üzərində məsələləri həll edirik. $k (i \leq k < j)$ k~(i \le k < j) elə bir dəyərini axtarırıq ki, $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1 cəmi minimal olsun. $1$ əlavə kəsmənin bir kəsim olaraq $s_{k}$ s_k və $s_{k + 1}$ s_{k+1} simvolları arasında edildiyini göstərir. Beləliklə, aşağıdakı rekurrent əlaqəni əldə edirik:

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)

Misal

Məsələn, " $abab cc b$ " adlı $7$ simvolluq sətir üçün bizdə var:

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)

Cəm $k = 3$ k = 3 üçün ən kiçik dəyərləri alır:

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

Çünki " $aba$ " və " $b cc b$ " sətirləri palindromdur, bu səbəbdən $f (1, 3) = f (4, 7) = 0$ f(1, 3) = f(4, 7) = 0.

Alqoritmin həyata keçirilməsi

Konstantalar, giriş sətiri $s$ və işçi massivləri elan edək.

#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) funksiyası, alt sətir $s_{i} ... s_{j}$ s_i~...~s_j-nin palindrom olub-olmadığını yoxlayır. Alt sətir $s_{i} ... s_{j}$ s_i~...~s_j palindromdur əgər $s_{i} = s_{j}$ s_i = s_j və $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} palindromdur. $I s P a l (i, j)$ IsPal(i, j)-nin dəyərlərini $p a l [i] [j]$ pal[i][j] massivinin hüceyrələrində saxlayırıq.

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) funksiyası, alt sətir $s_{i} ... s_{j}$ s_i~...~s_j-ni palindrom bölməsinə görə lazım olan minimal kəsim sayını qaytarır.

int f(int i, int j)
{

Əgər $i = j$ i = j, alt sətir $s_{i} ... s_{j}$ s_i~...~s_j bir simvoldan ibarətdir və onu kəsmək mənasızdır. Əgər $i > j$ i > j, alt sətir $s_{i} ... s_{j}$ s_i~...~s_j boş hesab olunur və kəsimlər də tələb olunmur.

  if (i >= j) return 0;

Əgər $f (i, j)$ f(i, j) dəyəri əvvəllər hesablanıbsa, bu dəyəri $d p [i] [j]$ dp[i][j] massivindən geri qaytarırıq.

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

Əgər alt sətir $s_{i} ... s_{j} (i < j)$ s_i~...~s_j~(i < j) palindromdursa, onu kəsmək mənasızdır. Bu halda minimal kəsim sayı $0$ olur.

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

Alt sətir $s_{i} ... s_{j}$ s_i~...~s_j-ni iki hissəyə bölək: $s_{i} ... s_{k} (i \leq k)$ s_i~...~s_k~(i \le k) və $s_{k + 1} ... s_{j} (k + 1 \leq j)$ s_{k+1}~...~s_j~(k + 1 \le j). Daha sonra hər iki hissə üçün rekursiv olaraq məsələləri həll edirik: $s_{i} ... s_{k}$ s_i~...~s_k və $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. $k (i \leq k < j)$ k~(i \le k < j) elə bir dəyərini axtarırıq ki, $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1 cəmi ən kiçik olsun.

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

Cavabı geri qaytarırıq $d p [i] [j] = f (i, j)$ dp[i][j] = f(i, j).

  return dp[i][j];
}

Proqramın əsas hissəsi. Giriş sətirini oxuyuruq.

cin >> s;

Massivləri ilkinləşdiririk.

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

Cavabı hesablayır və çıxışa yazırıq.

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