题解 P5839 【[USACO19DEC]Moortal Cowmbat】

wh_ZH · 2019-12-20 18:05:15 · 题解

本场USACO其他题目的题解

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

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

首先直接用原矩阵的交换方法不一定最优，拿到手先跑一遍 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;
}