本场USACO其他题目的题解

既然都写过了就在题解区再发一遍

给定一个字符串和一个 $M\times M$ 的矩阵 $a$，表示可以消耗 $a_{i,j}$ 的代价把字符 $i$ 改成字符 $j$，求把原字符串改成每个连续段长度都不小于 $K$ 的最小代价。

$n,K\le 10^5,M\le 26$

首先直接用原矩阵的交换方法不一定最优，拿到手先跑一遍 floyd。

然后考虑 dp ，$f_i$ 表示前 $i$ 个中每个连续段都 $\ge k$ 的最小代价，显然有转移

其中 $cost(i,j,c)$ 表示把 $[i,j]$ 全都改成字符 $c$ 的最小代价，这个可以前缀和预处理。

观察转移，发现可以在枚举到 $i$ 时再把 $i-k$ 的决策加进去，这样维护一个前缀 $\min$ 即可做到 $O(1)$ 转移。

复杂度 $O(n\times M)$

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int c[30][30],f[N];
char s[N];
int sum[30][N];
int query(int x,int l,int r){
	return sum[x][r]-sum[x][l-1];
}
int mn[30];
int main (){
	freopen ("cowmbat.in","r",stdin);
	freopen ("cowmbat.out","w",stdout);
	int n,m,k;scanf ("%d%d%d",&n,&m,&k);
	scanf ("%s",s+1);
	for (int i=0;i<m;i++)
		for (int j=0;j<m;j++)
			scanf ("%d",&c[i][j]);
	for (int l=0;l<m;l++)
		for (int i=0;i<m;i++)
			for (int j=0;j<m;j++)
				if (i!=j&&j!=l&&i!=l)
					c[i][j]=min(c[i][j],c[i][l]+c[l][j]);
	for (int i=0;i<m;i++)
		for (int j=1;j<=n;j++)
			sum[i][j]=c[s[j]-'a'][i]+sum[i][j-1];
	memset (mn,0x3f,sizeof(mn));
	memset (f,0x3f,sizeof(f));f[0]=0;
	for (int i=k;i<=n;i++)
		for (int j=0;j<m;j++)
			mn[j]=min(mn[j]+c[s[i]-'a'][j],f[i-k]+query(j,i-k+1,i)),f[i]=min(f[i],mn[j]);
	printf ("%d",f[n]);
	return 0;
}