记录编号	603458	评测结果	AAAAAAAAAAAAAAAA
题目名称	3321.[USACO19 DEC Gold]Moortal Cowmbat	最终得分	100
用户昵称	小福鑫	是否通过	通过
代码语言	C++	运行时间	0.270 s
提交时间	2025-07-12 16:31:14	内存使用	18.35 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,a[101][101],dis[101][101],f[1000001],nwt,ss[1000001][31],q[1000001];
char s[1000001];
signed main(){
	freopen("cowmbat.in","r",stdin);
	freopen("cowmbat.out","w",stdout);
	cin>>n>>m>>k;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		f[i]=q[i]=2e9;
	}
	f[0]=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			cin>>dis[i][j];
		}
	}
	for(int kk=1;kk<=m;kk++){
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){
				if(i!=j&&j!=kk&&i!=kk){
					dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ss[i][j]=ss[i-1][j]+dis[s[i]-'a'+1][j];
		}
	}
	for(int i=k;i<=n;i++){
		for(int j=1;j<=m;j++){
			q[j]=min(q[j]+dis[s[i]-'a'+1][j],f[i-k]+ss[i][j]-ss[i-k][j]);
			f[i]=min(f[i],q[j]);
		}
	}
	cout<<f[n];
}