思路
因为题目直接给出的改键时间不一定是最短的，先跑一遍 floyd，找出一个字母改成其他字母的最小时间。再构造一个前缀表，方便我们计算批量改键的时间，最后 dp 即可求出答案。
然后用前缀和变一下：$\min(dp_j+c_i-c_j)$ 然后 $c_i$ 是定值，找之前最小的 $dp_j-c_j$ 即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
int f[101][101],sum[100001][101],n,m,k,dp[101],ans[1000001];
//sum数组为前缀表，dp数组代表结尾为i的改键方案的花费时间，ans数组代表改前i个键的最小时间
char s[100001];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
cin>>s;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
cin>>f[i][j];//代表把i改成j的时间
}
}
for(int l=1;l<=m;l++){//floyd
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(f[i][j]>f[i][l]+f[l][j]){
f[i][j]=f[i][l]+f[l][j];
}
}
}
}
for(int i=1;i<=n;i++){//前缀表
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+f[s[i-1]-'a'+1][j];
}
}
memset(dp,0x3f,sizeof(dp));//初始化
memset(ans,0x3f,sizeof(ans));//初始化
ans[0]=0;//初始化
for(int i=k;i<=n;i++){
for(int j=1;j<=m;j++){
dp[j]=min(dp[j]+f[s[i-1]-'a'+1][j],ans[i-k]+sum[i][j]-sum[i-k][j]);
ans[i]=min(ans[i],dp[j]);//更新最优解
}
}
cout<<ans[n];
}
```