Moortal Kombat#10292

Moortal Kombat (Həll təhlili)

Алqoritm Floyd-Warshall-ı $a_{ij}$ a_{ij} matrisində işə salırıq ki, hər bir hərfi istənilən digər hərfə dəyişmək üçün ən qısa müddəti təyin etsin.

Matrisin xərclərini $cs t$ matrisini yaradacağıq ki, $cs t [i] [j] (1 \leq i \leq n)$ cst[i][j]~(1 \le i \le n) $s [i - 1]$ s[i - 1] hərfini $j$ hərfinə dəyişməyin ən az gün sayını saxlasın.

Daha sonrakı hesablama üçün dünyanın hissə cəmləri olan matris $p s$ quraraq xərclər matrisinin xərclərini içərən xüsusiyyət təqdim edirik:

p s [i] [j] = cs t [i] [1] + cs t [i] [2] + ... + cs t [i] [j]

ps[i][j] = cst[i][1] + cst[i][2] + ... + cst[i][j]

$d p [i] [j]$ dp[i][j] $s$ sətirinin ilk $i$ hərflərini Bessinin yeni tələblərinə uyğun olmayan bir sətirə çevirmək üçün ən son $k$ hərfini son sətirdə $j$ hərfi ilə əvəzləməklə saxlamaq üçün ən az gün sayını saxlayırıq.

Dinamika tənliklərini yazıq:

$s$ sətirinin ilk $i - 1$ i - 1 hərfi artıq $j$ hərfi ilə sonlanan bir sətirə çevrilmişdir. O zaman biz sadəcə $s [i - 1]$ s[i - 1] hərfini $j$ ilə əvəz edirik ki, bu $cs t [i] [j]$ cst[i][j] gün davam edəcək.
$d p [i] [j] = d p [i - 1] [j] + cs t [i] [j]$
dp[i][j] = dp[i - 1][j] + cst[i][j]
Yeni sətirdə son $k$ hərfi $j$ olmalıdır, buna görə də $d p [i - k] [0], d p [i - k] [1], ..., d p [i - k] [m - 1]$ dp[i - k][0], dp[i - k][1], ..., dp[i - k][m - 1] dəyərlərini nəzərdən keçiririk. Onlar arasında ən kiçiyini seçirik. Yəni, $s$ sətirinin ilk $i - k$ i - k hərfini Bessinin yeni tələblərinə uyğun bir sətirə çevirmək və son $k$ hərfi $s [i - k], s [i - k + 1], ..., s [i - 1]$ s[i - k], s[i - k + 1], ..., s[i - 1] dəyişikliyinə sonra $j$ ilə edilir, bu xərcə baxır:

cs t [i - k + 1] [j] + cs t [i - k + 2] [j] + ... + cs t [i] [j]

cst[i - k + 1][j] + cst[i - k + 2][j] + ... + cst[i][j]

Bu yığıncağı sabit müddətmişdə hesablamaq üçün prefiks dizi $p s$ kullanışının:

cs t [i - k + 1] [j] + cs t [i - k + 2] [j] + ... + cs t [i] [j] = p s [i] [j] - p s [i - k] [j]

cst[i - k + 1][j] + cst[i - k + 2][j] + ... + cst[i][j] = ps[i][j] - ps[i - k][j]

$mn$ adlı əlavə bir dizini saxlamaq istəyirik ki,

mn [i] = min (d p [i] [0], d p [i] [1], ..., d p [i] [m - 1])

mn[i] = min(dp[i][0], dp[i][1], ..., dp[i][m - 1])

Bu vəziyyətin dinamikası üçün tənlik $(i \geq k)$ (i \ge k) belə olacaq:

d p [i] [j] = p s [i] [j] - p s [i - k] [j] + mn [i - k]

dp[i][j] = ps[i][j] - ps[i - k][j] + mn[i - k]

Sonra iki variantdan $d p [i] [j]$ dp[i][j] üçün ən kiçik olanı seçəcəyik.

Mesələ cavabı

mn [n] = min (d p [n] [0], d p [n] [1], ..., d p [n] [m - 1])

mn[n] = min(dp[n][0], dp[n][1], ..., dp[n][m - 1])

Yeni Bessi sözünün hansı $k$ hərfləri ilə tamamlanacağı bizim üçün əhəmiyyətli deyil.

Misal

Bu misalda ən yaxşı həlledici hərfi hərfdə uyğun $b$ ilə dəyişmək, sonra $d$ $e$ ilə və sonra $e$ c ilə dəyişməkdir. İxtisarların ümumi xərci $1 + 4 + 0 + 0 = 5$ 1 + 4 + 0 + 0 = 5 gün olacaqdır ki, nəticə sətiri $bb ccc$ görünüşündə olacaqdır.

$a_{ij}$ a_{ij} matrisi üzrə xərclər matris $cs t$ quracağıq. $p s$ matrisini də hesablayacağıq.

Bütün $d p [1] [j] (0 \leq j \leq 4)$ dp[1][j]~(0 \le j \le 4) dəyərləri $+ \infty$ olacaqdır, çünki zolağın uzunluğu $k = 2$ k = 2-dən az ola bilməz. Nəticə olaraq, $mn [1] = + \infty$ mn[1] = +∞.

Bir şey $d p [2] [j]$ dp[2][j] (0 ≤ j ≤ 4) dəyərlərini hesablamaq üçün baxlanacaq:

$d p [2] [0] = (" ab " \to " aa ") = c n t [$ dp[2][0] = ("ab" \to "aa") = cnt[' $a$ ' $] [$ ' $a$ ' $] + c n t [$ ] + cnt[' $b$ '][' $a$ ' $] = 0 + 2 = 2$ ] = 0 + 2 = 2;
$d p [2] [1] = (" ab " \to " bb ") = c n t [$ dp[2][1] = ("ab" \to "bb") = cnt[' $a$ ' $] [$ ' $b$ ' $] + c n t [$ ] + cnt[' $b$ '][][ $^{'}$ 'b $^{'}] = 1 + 0 = 1$ '] = 1 + 0 = 1;
$d p [2] [2] = (" ab " \to " cc ") = c n t [$ dp[2][2] = ("ab" \to "cc") = cnt[' $a$ '][ $^{'}$ 'c $^{'}] [] [$ '][][' $b$ '][][ $^{'}$ 'c $^{'}] = 4 + 4 = 8$ '] = 4 + 4 = 8;
$d p [2] [3] = (" ab " \to " dd ") = c n t [$ dp[2][3] = ("ab" \to "dd") = cnt[' $a$ '][][ $^{'}$ 'd $^{'}] [] [$ '][][' $b$ '][][ $^{'}$ 'd $^{''}$ '''] = 4 + 4 = 8 $; \item$ dp[2][4] = ("ab" "ee") = cnt[ $^{'}$ 'a $^{'}] [] [$ '][][' $e$ '][][ $^{'}$ 'b $^{'}] [] [$ '][][' $e$ '] = 4 + 4 = 8 $; \end{itemize}$ $mn [2] = min (d p [2] [0], d p [2] [1], d p [2] [2], d p [2] [3], d p [2] [4]) = 1$ mn[2] = min(dp[2][0], dp[2][1], dp[2][2], dp[2][3] , dp[2][4]) = 1 $Q i y m ə t i$ Qiyməti dp[3][j] (0 j 4) $t ə n l i y i$ tənliyi $d p [3] [j] = p s [3] [j] - p s [1] [j] + mn [1]$ dp[3][j] = ps[3][j] - ps[1][j] + mn[1] mn[1] = +∞ $o l d u g ˘ u u ¨ c \c u ¨ ni s t i f a d ə e d i l ə c ə k .$ olduğu üçün istifadə ediləcək. k=2 $o l d u g ˘ u u ¨ c \c u ¨ n$ olduğu üçün 3 $-də zarifliklər üşündə qurulmuş zarifliklər təsir edəcək: \begin{itemize} \item$ dp[3][0] = dp[2][0] + cst[ $^{'}$ 'c $^{'}] [] [$ '][][' $a$ '] = 2 + 5 = 7 ("aaa") $; \item$ dp[3][1] = dp[2][1] + cst[ $^{'}$ 'c $^{'}] [] [$ '][][' $b$ [] = 1 + 5 = 6 ("bbb") $; \item$ dp[3][2] = dp[2][2] + cst[ $^{'}$ 'c $^{'}] [^{'}] [$ ']['][' $c$ '][][ $^{'}$ '[] $^{'}] = 8 + 0 = 8 (" ccc ")$ '] = 8 + 0 = 8~("ccc");
$d p [3] [3] = d p [2] [3] + cs t [$ dp[3][3] = dp[2][3] + cst[' $c$ '][][ $^{'}$ 'd $^{'}] [] [$ '][]["] = 8 + 3 = 11 ("ddd") $; \item$ dp[3][4] = dp[2][4] + cst[ $^{'}$ 'c $^{'}] []^{'}] [$ '][]'][' $e$ '][]'][ $^{'}$ '] = 8 + 2 = 10 ("eee") $; \end{itemize} Qiyməti$ dp[4][0] $iki yolla əldə etmək mümkündür: \begin{itemize} \item$ dp[4][0] = dp[3][0] + cst[ $^{'}$ 'd $^{'}] []^{'}] [$ '][]'][' $a$ '][][ $^{''}] = 7 + 5 = 12 (" aaaa ")$ ''] = 7 + 5 = 12~("aaaa");

və ya

$d p [4] [0] = p s [4] [0] - p s [2] [0] + mn [2] = 12 - 2 + 1 = 11 (" bbaa ")$ dp[4][0] = ps[4][0] - ps[2][0] + mn[2] = 12 - 2 + 1 = 11~("bbaa");

İkinci xərc daha yaxşıdır, zolağın sonuna iki bərabər ' $a$ ' hərfi əlavə olunur. $mn [2] = 1$ mn[2] = 1 dəyəri " $bb$ " zərfi nəticəsində əldə edilir, yəni optimal xətir formalı dəqiq qurtaracaq " $bbaa$ ".

Alqoritm Tətbiqi

Aşağıdakı dizinləri elan edirik:

$a [i] [j]$ — hərfi $i$ -ni $j$ -lə əvəz etməyin minimum xərcidir.
$cs t [i] [j]$ cst[i][j] — orijinal $s [i]$ sətirinin i-ci hərfini (1-dən indeksasiyaçı) $j$ hərfinə əvəz etməyin xərcidir. Formal olaraq
$cs t [i] [j] = a [s [i - 1] -^{'} a^{'}] [j]$
cst[i][j] = a[s[i - 1] - 'a'][j]
hərfi dəyişməni asanlıqla tapmaq üçün $k$ dizi uzunluğunu içərir:
$p s [i] [j] = cs t [1] [j] + cs t [2] [j] + ... + cs t [i] [j]$
ps[i][j] = cst[1][j] + cst[2][j] + ... + cst[i][j]
$d p [i] [j]$ dp[i][j] — $s$ sətirinin ilk $i$ hərfini ilə uyğun bir sətirə çevirmək üçün minimum gün sayını saxlayan, sonların $k$ -hərfləri $j$ -də olmalıdır (zolaq qrupları olduğundan tələblər).
$mn [i]$ — bütün $d p [i] [j]$ dp[i][j]-dən olan bütün $j$ -lərdə minimum: ilk $i$ sənətləri üçün ən yaxşı həll.

#define MAXN 100005
#define ALPH 26
int a[ALPH][ALPH], cst[MAXN][ALPH], ps[MAXN][ALPH], dp[MAXN][ALPH], mn[MAXN];

Məlumatları oxuyuruq.

cin >> n >> m >> k;
cin >> s;
for (i = 0; i < m; i++)
for (j = 0; j < m; j++)
   cin >> a[i][j];

Floyd-Warshall alqoritmini matrisi $a$ -da işə salırıq. Bitdikdən sonra, $a [i] [j]$ hərfi $i$ -dən hərfi $j$ -ə dəyişdirmək üçün ən kiçik gün sayını saxlayır.

for (x = 0; x < m; x++)
for (i = 0; i < m; i++)
for (j = 0; j < m; j++)
  a[i][j] = min(a[i][j], a[i][x] + a[x][j]);

Bizdə $m \leq 26$ m \le 26 hərf var. Xərclər matris $cs t$ quracağıq belə ki, $cs t [i] [j] (1 \leq i \leq n)$ cst[i][j]~(1 \le i \le n) $n [i - 1]$ n[i - 1] hərfini $j$ hərfinə dəyişmək üçün ən kiçik gün sayını saxlasın. Bütün $s$ sətirindəki hərf sayı $0$ -dan başlayır.

Daha sonrakı hesablama üçün dünyanın sərhəd cəmləri olan $p s$ matrisini SAXLAYACAQ:

p s [i] [j] = cs t [i] [1] + cs t [i] [2] + ... + cs t [i] [j]

ps[i][j] = cst[i][1] + cst[i][2] + ... + cst[i][j]

for (i = 1; i <= n; i++)
for (j = 0; j < m; j++)
{
  cst[i][j] = a[s[i - 1] - 'a'][j];
  ps[i][j] = ps[i - 1][j] + cst[i][j];
}

Dizaynları initializasiya edirik.

memset(dp, 0x3f, sizeof dp);
memset(mn, 0x3f, sizeof mn);
mn[0] = 0;

$d p$ massivi massivlərin dəyərini hesablamaq üçün:

for (i = 1; i <= n; i++)
for (j = 0; j < m; j++)
{

Hazırkı xətir qutuların ən ucuzunu təyin edin. Orijinal $s [i - 1]$ s[i - 1] sətirinin $i$ -ci hərfini $j$ ilə əvəz edirik. Yəni:

Mövcud $i - 1$ i - 1 $j$ harf ilə sonlanan zarflar artıq dəyişdirilib;
$s [i]$ hərfidir $i$ -cü son zərf hərfini $j$ ;
xərci $d p [i - 1] [j] + cs t [i] [j]$ dp[i - 1][j] + cst[i][j] əvəzinə olan qiymətdir.

d p [i] [j] = min (d p [i] [j], d p [i - 1] [j] + cs t [i] [j]);

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

Köhnə xərc zərfini $k$ -lü yeni zərfə başlayır, bu yeni zərfə $j$ ilə $i$ şəklindəyə $k$ uzunluğu olur. Bunun üçün: