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

#include<iostream>
using namespace std;

const int MAXN = 1e5 + 5;
const int INNF = 1e9 + 7;
int sum[MAXN][27];
int f[27][27];
int dp[27];
int a[MAXN];
int n, m, k;
string s;

int val(char x){
	return x - 'a' + 1;
}

int main(){
	freopen("cowmbat.in","r",stdin);
	freopen("cowmbat.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> m >> k;
	cin >> s;
	s = ' ' + s;
	for(int i = 1;i <= m;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> f[i][j];
		}
	}
	for(int kk = 1;kk <= m;kk ++){
		for(int i = 1;i <= m;i ++){
			for(int j = 1;j <= m;j ++){
				if(f[i][j] > f[i][kk] + f[kk][j]){
					f[i][j] = f[i][kk] + f[kk][j];
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			sum[i][j] = sum[i - 1][j] + f[val(s[i])][j];
		}
	}
    for(int i = 1;i <= n;i ++) a[i] = INNF;
    for(int i = 1;i <= m;i ++) dp[i] = INNF;
    a[0] = 0;
	for(int i = k;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(i >= k) dp[j] = min(dp[j] + f[val(s[i])][j], a[i - k] + (sum[i][j] - sum[i - k][j]));
            a[i] = min(a[i], dp[j]);
        }
    }
	cout << a[n] << '\n';
	return 0;
}