自动搬运

查看原文

来自洛谷，原作者为

	yeshubo_qwq 我是 luxu。

搬运于2025-08-24 22:35:10，当前版本为作者最后更新于2022-01-20 11:42:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定一字符串，你需要在这个字符串中插入若干个字符，使字符串中包含目标字符串，并使花费的代价最少。

思路

暴力枚举每一个位置，用双指针求出从这个位置作为目标字符串的开头的代价，最后取最小即可。

这里为了方便，我们用数组存插入代价，数组下标对应是哪个字母的花费代价。

其他细节请看代码注释。

代码

#include<bits/stdc++.h>
using namespace std;
int f['Z'],i,mi,t,w,s;
string s1,s2;
int main(){
    cin>>s1>>s2>>f['A']>>f['C']>>f['G']>>f['T'];
    mi=2e9;
    for(i=0;i<s1.size();i++){
        t=i;w=0;//指针初始化
		s=0;//花费初始化 
        while(w<s2.size()){
            if(s1[t]==s2[w])++t,++w;//字母相同，两根指针同时向后移
            else s+=f[s2[w++]];//字母不同，累计花费，目标字符串指针向后移
        }
        mi=min(mi,s);
    }
    cout<<mi;
    return 0; 
}