7447. Sətri doğramaq

Verilmiş s sətrində qoşa duran eyni simvolları silmək olar. Bu əməliyyatı mümkün olana qədər icra etmək olar. Əvvəlcə Siz sətirdə istənilən sayda simvol seçib onları silə bilərsiniz. İcazə verilən əməliyyatı aparmaqla boş sətir əldə etmək üçün başlanğıcda silinəcək simvolların minimal sayını təyin edin.

Giriş. s (1 ≤ (s)-n uzunluğu ≤ 100) sətri verilir.

Çıxış. Əvvəlcədən silinəcək simvolların minimal sayını verməli.

Girişə nümunə

abbcddka

Çıxışa nümunə

2

HƏLLİ

dinamik proqramlama

Alqoritmin analizi

Tutaq ki, dp[l][r] = Calc(l, r) – qoşa duran eyni simvolları silməklə boş sətir almaq üçün, verilmiş sətirdən əvvəlcə silinəcək simvolların minimal sayıdır. Onda:

Calc(l, r) = 0, əgər l > r.

Calc(l, l) = 1.

Calc(l, r) = Calc(l + 1, r – 1), əgər s[l] = s[r].

Kənar simvollar eyni olarsa onda içdə qalan hissə əvvəl silinir, sonra da onlar yanaşı gələrək ləğv edilir.

Əgər birinci simvolu silsək Calc(l, r) = 1 + Calc(l + 1, r),

Əgər sonuncu simvolu silsək Calc(l, r) = 1 + Calc(l, r – 1), yaza bilərik

Sonuncu iki şərti aşaöıdakı kimi birləşdirmək olar: Məsələni [l; r] parçasında həll etmək üçün, onu auyrılıqda [l; i] və [i + 1; r] (l ≤ i < r) parçalarında həll edib ən kiçik nəticə alaq:

Calc(l, r) =

Məsələn, sətirdən birinci elementi silmək i = l halına ekvivalentdir (bu zaman Calc(l, l) = 1), Lakin, sonuncu elementin silinməsi i = r – 1 halına ekvivalentdir (Calc(r, r) = 1).

Məsələnin cavabı dp[0][n – 1] = Calc(0, n – 1) olar. Burada n – giriş sətrin uzunluğudur..

Alqoritmin realizə olunması

İşçi massivləri təyin edək.

#define MAX 102

#define INF 2100000000

int dp[MAX][MAX];

char s[MAX];

Qoy Calc(l, r) – məsələnin [l; r].parçasında həlli olsun

int Calc(int l, int r)

{

if (l > r) return 0;

if (l == r) return 1;

if (dp[l][r] != -1) return dp[l][r];

int &ans = dp[l][r] = INF;

if (s[l] == s[r])

ans = min(ans, Calc(l + 1, r - 1));

// ans = min(ans, 1 + Calc(l + 1, r));

// ans = min(ans, 1 + Calc(l, r - 1));

for (int i = l; i < r; i++)

ans = min(ans, Calc(l, i) + Calc(i + 1, r));

return ans;

}

Proqramın əsas hissəsi. Sətri oxuyuruq. Hesablayıb cavabı çıxarırıq Calc(0, n – 1).

gets(s);

n = strlen(s);

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

printf("%d\n",Calc(0, n - 1));