蓝桥杯2024年第十五届省赛真题-遗迹

解题思路:

ret放在最外层循环就AC了，但觉得后台数据应该错了，ret 觉得应该是放在 auto& k1 循环内的

前后结点相同的状态应该也有扩展状态的必要，而不是直接继承

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;

struct w{ int x,y,z;};

vector<w> pre[26];

int main(){

        int i,j,x,y,n,m,L,u=1,k,fl,c[N],ret;

        string s,t;

        cin>>n>>m>>L>>s>>t;

        for(i=0;i<n;i++)

            pre[s[i]-'a'].push_back(w{1,i,0});

        for(i=1;i<m;i++){

             x=t[i-1]-'a',y=t[i]-'a'; ret=INT_MAX;

             if(x==y)

                for(auto& k1 : pre[y]){

                    if(k1.x==u) k1.x=u+1;

                }

             else{

                 fl=0;

                 for(auto& k1 : pre[y]){

                     for(auto& k2 : pre[x])

                          if(k2.x==u){

                             int d=k2.z+abs(k1.y-k2.y);

                             ret=min(ret,d);

                         }

                     if(ret<=L) fl=1,k1.x=u+1,k1.z=ret;

                }

                if(!fl){ cout<<u; return 0;} 

             }

             ++u;

      }

     cout<<u; return 0;

}