Moortal Kombat (Розбір)

Поступимо за алгоритмом Флойда-Воршелла на матриці $a_{ij}$ a_{ij}, щоб визначити найкоротший час заміни кожної букви на будь-яку іншу.

Складемо матрицю витрат $cs t$ таку, що $cs t [i] [j] (1 \leq i \leq n)$ cst[i][j]~(1 \le i \le n) містить найменшу кількість днів, за яку можна змінити букву $s [i - 1]$ s[i - 1] на букву $j$ .

Для зручності подальших обчислень побудуємо матрицю $p s$ , що містить значення часткових сум матриці витрат $cs t$ за стовпцями:

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] містить найменшу кількість днів, за яку можна перетворити перші $i$ букв рядка $s$ в рядок, що задовольняє новим вимогам Бессі, причому останні $k$ букви в новому рядку будуть буквою $j$ .

Запишемо рівняння динаміки:

Нехай перша $i - 1$ i - 1 буква рядка $s$ вже перетворена в рядок, в якому останніми $k$ буквами стоїть буква $j$ . Тоді ми просто змінюємо букву $s [i - 1]$ s[i - 1] на $j$ , що можна зробити за $cs t [i] [j]$ cst[i][j] днів.
$d p [i] [j] = d p [i - 1] [j] + cs t [i] [j]$
dp[i][j] = dp[i - 1][j] + cst[i][j]
Щоб у новому рядку останніми $k$ буквами була буква $j$ , розглянемо значення $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]. Виберемо серед них найменше. Тобто перетворимо перші $i - k$ i - k букв рядка $s$ в рядок, що задовольняє новим вимогам Бессі (при цьому нам не важлива буква, якою буде закінчуватися підрядка довжини $i - k$ i - k, нам важливо отримати цей рядок за найменшу кількість днів). Після цього $k$ останніх букв $s [i - k], s [i - k + 1], ...,, s [i - 1]$ s[i - k], s[i - k + 1], ..., , s[i - 1] початкового рядка $s$ міняємо на букву $j$ , на що піде

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]

днів. Зазначену суму можна обчислити за константний час, використовуючи масив префіксів $p s$ :

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$ , де

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])

Таким чином, рівняння динаміки для цього випадку $(i \geq k)$ (i \ge k) матиме вигляд:

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]

Залишається серед двох варіантів для $d p [i] [j]$ dp[i][j] вибрати найменший.

Відповідь на задачу буде значення

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])

Нам не важливо, на які саме $k$ букви закінчується нове слово Бессі.

Приклад

У даному прикладі оптимальне рішення полягає в наступному: замінити $a$ на $b$ , потім $d$ на $e$ , а після цього обидві $e$ — на $c$ . Загальна вартість змін складе $1 + 4 + 0 + 0 = 5$ 1 + 4 + 0 + 0 = 5 днів, а підсумковий рядок матиме вигляд $bb ccc$ .

За матрицею $a_{ij}$ a_{ij} побудуємо матрицю витрат $cs t$ . Обчислимо також матрицю $p s$ .

Усі значення $d p [1] [j] (0 \leq j \leq 4)$ dp[1][j]~(0 \le j \le 4) будуть рівні $+ \infty$ , оскільки довжина смуги не може бути меншою $k = 2$ k = 2. Відповідно, $mn [1] = + \infty$ mn[1] = +∞.

Розглянемо процес обчислення значень dp[2][j] (0 ≤ j ≤ 4).

$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$ ' $] + c n t [$ ] + cnt[' $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$ ' $] + c n t [$ ] + cnt[' $b$ ' $] [$ ' $d$ ' $] = 4 + 4 = 8$ ] = 4 + 4 = 8;
$d p [2] [4] = (" ab " \to " ee ") = c n t [$ dp[2][4] = ("ab" \to "ee") = cnt[' $a$ ' $] [$ ' $e$ ' $] + c n t [$ ] + cnt[' $b$ ' $] [$ ' $e$ ' $] = 4 + 4 = 8$ ] = 4 + 4 = 8;

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

При обчисленні значень $d p [3] [j] (0 \leq j \leq 4)$ dp[3][j]~(0 \le j \le 4) рівняння

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] = + \infty$ mn[1] = +∞. Тому для отримання смуг з перших $3$ букв можна лише продовжити вже побудовані смуги довжини $2$ :

$d p [3] [0] = d p [2] [0] + cs t [$ dp[3][0] = dp[2][0] + cst[' $c$ ' $] [$ ' $a$ ' $] = 2 + 5 = 7 (" aaa ")$ ] = 2 + 5 = 7~("aaa");
$d p [3] [1] = d p [2] [1] + cs t [$ dp[3][1] = dp[2][1] + cst[' $c$ ' $] [$ ' $b$ ' $] = 1 + 5 = 6 (" bbb ")$ ] = 1 + 5 = 6~("bbb");
$d p [3] [2] = d p [2] [2] + cs t [$ 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 ")$ ] = 8 + 3 = 11~("ddd");
$d p [3] [4] = d p [2] [4] + cs t [$ dp[3][4] = dp[2][4] + cst[' $c$ ' $] [$ ' $e$ ' $] = 8 + 2 = 10 (" eee ")$ ] = 8 + 2 = 10~("eee");

Значення $d p [4] [0]$ можна отримати двома способами:

$d p [4] [0] = d p [3] [0] + cs t [$ dp[4][0] = dp[3][0] + cst[' $d$ '][' $a$ ' $] = 7 + 5 = 12 (" aaaa ")$ ] = 7 + 5 = 12~("aaaa");

або

$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");

Другий випадок оптимальніший, додаються дві букви ' $a$ ' до рядка з двох символів. Значення $mn [2] = 1$ mn[2] = 1 досягається на рядку " $bb$ ", а значить оптимальною строкою буде " $bbaa$ ".

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

Оголосимо робочі масиви:

$a [i] [j]$ — мінімальна вартість перетворення букви $i$ в букву $j$ .
$cs t [i] [j]$ cst[i][j] — вартість того, щоб $i$ -я буква початкового рядка $s$ (індексація починається з $1$ ) була замінена на букву $j$ . Формально
$cs t [i] [j] = a [s [i - 1] -^{'} a^{'}] [j]$
cst[i][j] = a[s[i - 1] - 'a'][j]
$p s$ — масив часткових сум по $cs t$ , щоб швидко знаходити вартість зміни підрядка довжини $k$ :
$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] — мінімальна кількість днів, щоб перетворити перші $i$ букви рядка $s$ у допустимий рядок (за правилами смуг), при цьому останні $k$ букви результату мають бути буквою $j$ .
$mn [i]$ — мінімум по всім $j$ з $d p [i] [j]$ dp[i][j]: краще рішення для перших $i$ символів.

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

Читаємо вхідні дані.

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

Запускаємо алгоритм Флойда-Воршелла на матриці $a$ . Після його завершення $a [i] [j]$ містить найменшу кількість днів, за яку можна змінити букву $i$ на букву $j$ .

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

У нас є $m \leq 26$ m \le 26 букв. Складемо матрицю витрат $cs t$ таку, що $cs t [i] [j] (1 \leq i \leq n)$ cst[i][j]~(1 \le i \le n) містить найменшу кількість днів, за яку можна змінити букву $s [i - 1]$ s[i - 1] на букву $j$ . Індексація букв у рядку $s$ починається з $0$ .

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

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

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

Вичислюємо значення ячеек масиву $d p$ . Букві $i$ відповідає символ $s [i - 1]$ s[i - 1]. Нумерація букв у змінній $j$ йде від $0$ (якій відповідає буква ' $a$ ') до $m - 1$ m - 1. Інтуїтивно на кожному кроці $i$ Бессі вирішує:

або продовжувати ту ж кнопку, що й раніше,
або почати нову смугу довжиною як мінімум $k$ .

Ми обираємо те, що дешевше, і записуємо результат в $d p [i] [j]$ dp[i][j].

Цикл по $i$ починаємо з $k$ , тому що перша допустима смуга може закінчитися лише на позиції $k$ .

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

Продовжуємо поточну смугу. Букву початкового рядка $s [i - 1]$ s[i - 1] змінюємо на $j$ . Тобто:

попередні $i - 1$ i - 1 букв вже перетворені і закінчуються на $j$ ;
тепер додаємо $i$ -ю букву $s [i - 1]$ s[i - 1], теж робимо її $j$ ;
вартість складе $d p [i - 1] [j] + cs t [i] [j]$ dp[i - 1][j] + cst[i][j].

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

Починаємо нову смугу з $k$ букв. Вважаємо, що на позиції $i$ закінчується нова смуга довжиною рівно $k$ (або більше), що складається з букви $j$ . Для цього:

Беремо краще перетворення перших $(i - k)$ (i - k) букв (все, що було раніше): $mn [i - k]$ mn[i - k].
Додаємо вартість заміни останніх $k$ букв (від $i - k + 1$ i - k + 1 до $i$ ) на $j$ :

p s [i] [j] - p s [i - k] [j]

ps[i][j] - ps[i - k][j]

  dp[i][j] = min(dp[i][j], ps[i][j] - ps[i - k][j] + mn[i - k]);

Після обчислення всіх $d p [i] [j]$ dp[i][j] для фіксованого $i$ , зберігаємо найкраще (мінімальне) значення серед усіх $j$ в $mn [i]$ .

  mn[i] = min(mn[i], dp[i][j]);
}

Виводимо відповідь.

cout << mn[n] << "\n";