题解：CF1701E Text Editor

· · 题解

CF1701E Text Editor

最优解有两种情况：

  1. 只从后往前移动或删除字符。
  2. 从后往前移动或删除字符，然后按下 Home 键，在从前往后移动和删除字符。

对于第一种情况，直接求大力求 LCP 长度 len，答案就是 n-len（前提是有解）。

对于第二种情况，贪心地想，在后面删几下，按 Home 键，再在前面删几下，再按 End 键，再在在后面删几下的方案一定不如在后面删完后再按 Home 键把前面删完。

因此我们可以将 s 分为三部分：左、中、右。表示先在后面（右部分）删完，按 Home 键，跳到前面（左部分）删完，中间部分完全不删。你会发现这个时候其实 End 键没用了。

先假设一开始每个字符有 1 代价，接下来左部分要删的字符既要删除又要移动，代价为 2，比一开始大 1，中部字符不用操作，代价为 0，比一开始小 1。因此，需要最大化一段不删除区间的长度减去它前面已删除数的数量（即下图打大括号部分字符的贡献）。

所以定义状态 f_{i,j,k} 表示在 s_1 \sim s_i 中操作，使其与 t_1 \sim t_j 相等，且 1\sim i 中最后一次连续的不删除操作有 k 个字符的最大贡献，则有如下转移方程：

  1. 当 s_i=t_j 时，f_{i,j,k}=f_{i-1,j-1,k-1}。
  2. 当 k = 0 时，f_{i,j,k}=\max\limits_{l=0}^{j}[\max(f_{i-1,j,l},l+j-i)]。

但该转移方程需要最后一次操作是删除才能更新 f 值，因此最后一次操作，不删除字符不会被更新，在 s 结尾加一个不可能出现的字符（如#）强迫其删除并更新。

该转移方程空间复杂度和时间复杂度均为 O(n^3)，过不了此题。空间用滚动数组优化即可，下面考虑如何优化时间。

式子 2 只修改 O(n) 个状态，每个状态从 O(n) 个状态转移过来。\max(f_{i-1,j,l}) 可以维护前缀最大值优化。\max(l+j-i) 可以通过维护最大合法的 l 优化。

式子 1 只有赋值，相当于给满足 s_i=t_j 的 f_{i-1,j-1} 向右向下移动一位。可用链表优化：向右移动可以使用链表或队列在开头插入元素，并把结尾超出范围的元素删掉来实现，向下移动则可通过 O(1) 交换 f_{i-1,j-1} 和 f_{i-1,j} 两个链表实现。同时，经过链表优化后，式子 2 中最大合法的 l 其实就是链表的大小减去 1。

经过以上优化，代码时间复杂度和空间复杂度均为 O(n^2)，可通过此题。代码使用 STL 中的 list 实现（想要快点可以手写），常数较大，运行时间为 1999 毫秒。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5005;
int t,n,m,mx[N];
pair<int,int>tmx[N];
char a[N],b[N];
list<int>f[N];
inline void solve(){
    cin>>n>>m>>a+1>>b+1;
    a[n+1]='#';
    a[n+2]=0;
    ++n;
    for(int i=0;i<=m;i++)f[i].clear(),tmx[i]={0x80808080,0x80808080},mx[i]=0x80808080;
    f[0].push_back(0);
    mx[0]=0;
    tmx[0]={0,0x80808080};
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            if(a[i]==b[j]){
                f[j].swap(f[j-1]);
                swap(mx[j],mx[j-1]);
            }
        }
        for(int j=m;j>=1;j--){
            if(a[i]!=b[j]){
                f[j].clear(),mx[j]=0x80808080;
            }
        }
        for(int j=m;j>=1;j--){
            if(a[i]==b[j]&&!f[j].empty()){
                f[j].push_back(0x80808080);
                if(f[j].size()>j+1)f[j].pop_front();
            }
        }
        for(int j=0;j<=m;j++){
            if(max(tmx[j].first,tmx[j].second)==0x80808080)continue;
            if(f[j].empty())f[j].push_back(0x80808080);
            f[j].back()=max(f[j].back(),max(tmx[j].first,tmx[j].second));
            mx[j]=max(mx[j],f[j].back());
        }
        for(int j=0;j<=m;j++){
            if(!f[j].empty())tmx[j]={mx[j],int(f[j].size())-1+j-i};
            else tmx[j]={0x80808080,0x80808080};
        }
//      for(int j=0;j<=m;j++){
//          cout<<mx[j]<<','<<f[j].size()<<' ';
//      }
//      cout<<'\n';
    }
    if(f[m].empty())cout<<"-1\n";
    else{
        --n;
        int r=1+n-f[m].front();
        int z=0,s=0;
        for(int i=1;i<=n;i++){
            if(i>m||a[i]!=b[i]){
                break;
            }else{
                ++z;
            }
        }
        s=n-z;
        cout<<min(r,s)<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}