import {Title, Resources, ResourceItem, QList, Q, Focus} from "@/lib/noip"

Moortal Combat

这题考了以下知识点：N到N最短路 + DP + prefix sum

N到N最短路可以通过Floyd-Warshall算法来求。

DP构造有难度（主要是K可能很大），直观的想法是：前ii个字母中固定最后一个字母和最后一个streak长度。这个不行，空间太大。

正确的DP构造，不需要streak长度这一维，可以直接在合法的串上做DP，扩展的时候有两种情况：

具体见下面代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m, K;
int a[26][26];  // <= 1000
char s[100005];
int dp[100005][26]; // dp[i][j]: cheapest cost of 0..i, last letter is j
const int INF = 1e9;
int ps[26][100005]; // prefix sum of distance
 
int main() {
    scanf("%d %d %d", &n, &m, &K);
    scanf("%s", s);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
 
    // floyd-warshall
    for (int k = 0; k < m; k++)
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
 
    // prefix sum
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            ps[i][j+1] = ps[i][j] + a[s[j]-'a'][i];
 
    // dp
    for (int i = 0; i < n; i++)
        fill(dp[i], dp[i]+m, INF);
    for (int i = K-1; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (i == K-1) {     // base case
                dp[i][j] = ps[j][i+1] - ps[j][i+1-K];
                continue;
            }
            // continue last letter
            dp[i][j] = dp[i-1][j] + a[s[i]-'a'][j];
            for (int k = 0; k < m; k++) {
                // change from any letter to j exactly K letters ago
                if (k != j)
                    dp[i][j] = min(dp[i][j], dp[i-K][k] + ps[j][i+1] - ps[j][i+1-K]);
            }
        }
 
    int ans = INF;
    for (int i = 0; i < m; i++)
        ans = min(ans, dp[n-1][i]);
    printf("%d", ans);
 
    return 0;
}