显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int M=30,N=1e5+10,inf=1e7;
int read(){
int x=0,f=1;
char c=getchar();
while(c<48||c>57){
if(c==45) f=-1;
c=getchar();
}
while(c>=48&&c<=57){
x=x*10+c-48;
c=getchar();
}
return f*x;
}
int n,m,q,w;
int a[N];
int dp[M][M];
char s;
int sum[M][N];
//先字符,后位置
int mn[M],f[N];
int main(){
freopen("cowmbat.in","r",stdin);
freopen("cowmbat.out","w",stdout);
n=read();m=read();q=read();
for(int i=1;i<=n;i++){
cin>>s;
a[i]=s-96;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
dp[i][j]=read();
for(int k=1;k<=m;k++)
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
for(int k=1;k<=m;k++){//字符
for(int i=1;i<=n;i++){//位置
sum[k][i]=sum[k][i-1];
sum[k][i]+=dp[a[i]][k];
}
}
memset(mn,0x3f,sizeof(mn));
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=q;i<=n;i++){//位置
for(int j=1;j<=m;j++){//字符
w=sum[j][i]-sum[j][i-q];
mn[j]=min(mn[j]+dp[a[i]][j],f[i-q]+w);
f[i]=min(f[i],mn[j]);
}
}
printf("%d",f[n]);
return 0;
}