P8013 题解

yeshubo_qwq · 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; 
}