记录编号 603459 评测结果 AAAAAAAAAAAAAAAA
题目名称 3321.[USACO19 DEC Gold]Moortal Cowmbat 最终得分 100
用户昵称 Gravatar会挽弯弓满月 是否通过 通过
代码语言 C++ 运行时间 0.334 s
提交时间 2025-07-12 16:31:37 内存使用 10.12 MiB
显示代码纯文本
#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;
}