Moortal Kombat (Çözgüdiň düşündirişi)

Let's run the Floyd – Warshall algorithm on the matrix a_{ij} to determine the shortest time required to replace each letter with any other letter.

Then construct a cost matrix $cst$, where cst[i][j]~(1 \le i \le n) represents the minimum number of days needed to change the letter s[i - 1] into the letter $j$.

For convenience in further calculations, we build a matrix $ps$ that contains the column-wise prefix sums of the cost matrix $cst$:

Let dp[i][j] denote the minimum number of days required to transform the first $i$ letters of the string $s$ into a string that satisfies Bessie’s new requirements, with the last $k$ letters of the new string being the letter $j$.

We can write the dynamic equations as follows:

• Suppose the first i - 1 letters of $s$ уhave already been transformed into a string whose last $k$ letters are all $j$. Then we simply change the letter s[i - 1] to $j$, which can be done in cst[i][j] days.

  dp[i][j] = dp[i - 1][j] + cst[i][j]

• To ensure that the last $k$ letters of the new string are all $j$, consider the values dp[i - k][0], dp[i - k][1], ..., dp[i - k][m - 1]. Choose the smallest among them — that is, we transform the first i - k letters of $s$ into a string satisfying Bessie's new requirements (we don't care which letter the substring of length i - k ends with; we only care that it can be obtained in the minimum number of days). After that, we replace the last $k$ letters of the original string $s$ — namely s[i - k], s[i - k + 1], ..., , s[i - 1] — with the letter $j$, which takes

days. This sum can be computed in constant time using the prefix sum array $ps$:

We maintain an auxiliary array $mn$, where

Thus, the dynamic programming equation for this case (i \ge k) takes the following form:

It remains to choose the smaller of the two options for dp[i][j].

The answer to the problem is the value

We don't care which particular $k$ letters the new word Bessie ends with.

Example

In this example, the optimal solution is as follows: replace $a$ with $b$, then $d$ with $e$, and after that replace both $e$'s with $c$. The total cost of the changes is 1 + 4 + 0 + 0 = 5 days, and the resulting string will be $bbccc$.

Using the matrix a_{ij}, we construct the cost matrix $cst$. We also compute the matrix $ps$.

All values of dp[1][j]~(0 \le j \le 4) will be equal to $+\infty$, since the length of the stripe cannot be less than k = 2. Accordingly, mn[1] = +∞.

Let us now consider the process of computing the values of dp[2][j] (0 ≤ j ≤ 4).

• dp[2][0] = ("ab" \to "aa") = cnt['$a$'$][$'$a$'] + cnt['$b$']['$a$'] = 0 + 2 = 2;

• dp[2][1] = ("ab" \to "bb") = cnt['$a$'$][$'$b$'] + cnt['$b$'$][$'$b$'] = 1 + 0 = 1;

• dp[2][2] = ("ab" \to "cc") = cnt['$a$'$][$'$c$'] + cnt['$b$'$][$'$c$'] = 4 + 4 = 8;

• dp[2][3] = ("ab" \to "dd") = cnt['$a$'$][$'$d$'] + cnt['$b$'$][$'$d$'] = 4 + 4 = 8;

• dp[2][4] = ("ab" \to "ee") = cnt['$a$'$][$'$e$'] + cnt['$b$'$][$'$e$'] = 4 + 4 = 8;

When computing the values of dp[3][j]~(0 \le j \le 4), the equation

will not be used, since mn[1] = +∞. Therefore, to obtain strips from the first three letters, one can only extend the strips of length two that have already been constructed:

• dp[3][0] = dp[2][0] + cst['$c$'$][$'$a$'] = 2 + 5 = 7~("aaa");

• dp[3][1] = dp[2][1] + cst['$c$'$][$'$b$'] = 1 + 5 = 6~("bbb");

• dp[3][2] = dp[2][2] + cst['$c$'$][$'$c$'] = 8 + 0 = 8~("ccc");

• dp[3][3] = dp[2][3] + cst['$c$'$][$'$d$'] = 8 + 3 = 11~("ddd");

• dp[3][4] = dp[2][4] + cst['$c$'$][$'$e$'] = 8 + 2 = 10~("eee");

The value of $dp[4][0]$ can be obtained in two ways:

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

or

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

The second case is more optimal — two letters '$a$' are appended to a two-character string. The value mn[2] = 1 is achieved for the string "$bb$", which means the optimal string is "$bbaa$".

Algorithm implementation

Let us define the following arrays:

• $a[i][j]$ — the minimum cost of transforming letter $i$ into letter $j$.

• cst[i][j] — the cost of replacing the $i$-th letter of the original string $s$ (indexing starts from $1$) with letter $j$. Formally

  cst[i][j] = a[s[i - 1] - 'a'][j]

• $ps$ — the prefix sum array of $cst$, used to quickly compute the cost of changing a substring of length $k$:

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

• dp[i][j] — the minimum number of days required to transform the first $i$ letters of string $s$ into a valid string (according to the stripe rules), where the last $k$ letters of the result are letter $j$.

• $mn[i]$ — the minimum over all $j$ of dp[i][j], i.e. the best solution for the first $i$ characters.

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

Read the input data.

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

Run the Floyd - Warshall algorithm on the matrix $a$. After it finishes, $a[i][j]$ contains the minimum number of days required to change letter $i$ into letter $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]);

We have m \le 26 letters. Let us construct a cost matrix $cst$ such that cst[i][j]~(1 \le i \le n) contains the minimum number of days required to change the letter s[i - 1] into letter $j$. The letters in the string $s$ are indexed starting from $0$.

For convenience in further computations, we'll build a matrix $ps$, which contains the column-wise prefix sums of the cost matrix $cst$:

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

Initialize the arrays.

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

We compute the values of the $dp$ array cells. The letter $i$ corresponds to the character s[i - 1]. The letters in variable $j$ are numbered from $0$ (corresponding to letter '$a$') to m - 1. Intuitively, at each step $i$, Bessie decides:

• either to continue pressing the same button as before,

• or to start a new stripe of length at least $k$.

We choose the cheaper option and save the result in dp[i][j].

We start the loop over $i$ from $k$ because the first valid stripe can only end at position $k$.

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

We continue the current stripe. The letter s[i - 1] of the original string is changed to $j$. That is:

• the previous i - 1 letters have already been transformed and end with $j$;

• now add the $i$-th letter s[i - 1], also turning it into $j$;

• the total cost will be dp[i - 1][j] + cst[i][j].

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

We start a new stripe of $k$ letters. We assume that at position $i$ a new stripe of exactly $k$ (or more) letters ends, consisting of the letter $j$. To do this:

• Take the best transformation of the first (i - k) letters (everything before the new stripe): mn[i - k].

• Add the cost of replacing the last $k$ letters (from i - k + 1 to $i$) with $j$:

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

After computing all dp[i][j] for a fixed $i$, we store the best (minimum) value among all $j$ in $mn[i]$.

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

Print the answer.

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