[JOIG 2024] 名前 / Name 题解

· · 题解

套路地考虑动态规划：如果令 f_{i,j} 表示匹配完了 S 的前 i 位和 T 的前 j 位的答案，你发现它没办法转移。

考虑增加状态：有一种比较朴素的方法是记录答案的最后 K 位，这样确实是正确的，但是时间、空间复杂度都需要乘以一个 |\Sigma|^3（其中 |\Sigma|=52，表示字符集大小），过不了题。

接着观察到上面很多状态都是冗余的，因为我们只需要关心 S 和 T 的最后 K 个字符。继续考虑记下答案的最后 K 个字符，但是使用 unordered_map 存储状态并且使用 BFS 转移——因为大多数情况下只会使用 S 和 T 中的字符，若使用其他字符那么都是等价的；于是对于使用非 S 和 T 中字符的情况，通通用 * 或者某个其他字符来代替，这样能大大压缩状态数量，但是常数会上天。我在 VP 的时候实现了这种做法，可以获得 70 分。

继续观察性质，考虑是否存在一些比较简洁且便于转移的状态。由于只需要记最后 K 个字符，所以我们只用关心它们是否来自 S 或 T（事实上这样就可以在转移过程中从状态“还原”这些字符，只需要从 S / T 的当前位置倒着推回去就可以得出；从而使得转移更加简洁明了）：使用二进制状态压缩这 K 个字符，其中如果二进制数的从右到左第一位为 1 表示它来自 S，反之亦然；第二位为 1 表示它来自 T，反之亦然（使用二进制数的原因是这个字符可能同时来自 S / T 或者同时不来自 S / T，后者即为上面所述的 * 的情况），时间复杂度后面乘上的系数就是 4^K\le 64，可以接受。根据定义直接枚举下一个字符需要是 S 或 T 中的字符，或者是一个 *，即可完成转移。

时间复杂度 O(NM4^K)。转移的时候使用 BFS 的写法可能比较简便。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void chmin(int &x,int y){if(y<x)x=y;}
const int I=1e18;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m,k; string s,t; cin>>n>>m>>k>>s>>t;
  vector f(n+1,vector(m+1,vector(4,vector(4,vector<int>(4,I)))));
  queue<tuple<int,int,int,int,int> > q;
  f[0][0][0][0][0]=0,q.emplace(0,0,0,0,0);
  auto upd=[&](int u,int v,int x,int y,int z,int w){
    if(f[u][v][x][y][z]==I)q.emplace(u,v,x,y,z);
    chmin(f[u][v][x][y][z],w);
  }; // 状态转移
  while(!q.empty()){
    auto [u,v,x,y,z]=q.front(); q.pop();
    if(u==n&&v==m)cout<<f[u][v][x][y][z]<<endl,exit(0);
    vector<int> c={x,y,z};
    if(u<n&&v<m&&s[u]==t[v]){
      bool w=true;
      for(int i=0,a=u-1,b=v-1;i<k;i++){
        if(c[i]&1&&s[u]==s[a--])w=false;
        if(c[i]>>1&1&&s[u]==t[b--])w=false;
      } // 还原出最后 k 个字符，判断是否能进行转移
      if(w)upd(u+1,v+1,3,x,y,f[u][v][x][y][z]+1);
    }
    else{
      if(u<n){
        bool w=true;
        for(int i=0,a=u-1,b=v-1;i<k;i++){
          if(c[i]&1&&s[u]==s[a--])w=false;
          if(c[i]>>1&1&&s[u]==t[b--])w=false;
        }
        if(w)upd(u+1,v,1,x,y,f[u][v][x][y][z]+1);
      }
      if(v<m){
        bool w=true;
        for(int i=0,a=u-1,b=v-1;i<k;i++){
          if(c[i]&1&&t[v]==s[a--])w=false;
          if(c[i]>>1&1&&t[v]==t[b--])w=false;
        }
        if(w)upd(u,v+1,2,x,y,f[u][v][x][y][z]+1);
      }
    }
    upd(u,v,0,x,y,f[u][v][x][y][z]+1); // 加入一个 *
  }
  return 0;
}