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

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m,k,a[30][30],prz[30];
char s[100010];
ll sum[30][100010],f[100010];

int main(){
	freopen("cowmbat.in","r",stdin);
	freopen("cowmbat.out","w",stdout);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%lld %lld %lld",&n,&m,&k);
	scanf("%s",s+1);
	for (int i=0;i<m;++i)
		for (int j=0;j<m;++j)
			scanf("%lld",&a[i][j]);
	for (int k=0;k<m;k++)
		for (int i=0;i<m;i++)
			for (int j=0;j<m;j++)
				if (i!=j&&i!=k&&j!=k)
					a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	for (int i=0;i<m;i++)
		for (int j=1;j<=n;j++)
			sum[i][j]=a[s[j]-'a'][i]+sum[i][j-1];
	memset (prz,0x3f,sizeof(prz));
	memset (f,0x3f,sizeof(f));
	f[0]=0;
	for (int i=k;i<=n;i++)
		for (int j=0;j<m;j++){
			prz[j]=min(prz[j]+a[s[i]-'a'][j],f[i-k]+sum[j][i]-sum[j][i-k]);
			f[i]=min(f[i],prz[j]);
		}
	printf("%lld",f[n]);
	return 0;
}