题解：P12129 [蓝桥杯 2024 省 B 第二场] 遗迹（加强版）

· · 题解

前情提要：由于两个字符串数组大小写反，硬控我半个小时。

考虑动态规划。

我们设一个状态 dp_{i,j}，用来表示此时此刻，这个指针处于键盘的第 i 位的时候已经打到了字符串 t 的第 j 位所需的最小步数，很显然如果 \min(dp_{i,j}) \le L 的话，这个长度为 j 的前缀就是能够到达的，即我们可以更新答案。

那该怎么转移呢？

对于一个位置 k 肯定是从它的左边或者右边过来，所以我们就可以用两次循环来解决这个问题。我们每一次都去寄存从它左边或者从它右边过来到这个位置的最小值，这里可以用一个单调栈来解决。但是可能有人会对此有疑问，大致可能就是光去寄存 dp_{i,j-1} 最小值还远远不够。因为从位置 i 转移到位置 k 还有路径贡献，也就是还有转移路径。那为什么可以直接统计呢？那是因为我们可以发现，转移路径的步数增加是对所有转移的结果，即现在更优的在以后也肯定更优。

所以我们就可以写出动态转移方程：dp_{k,j}= \min(dp_{i,j-1}+len(i,k))，其中 len(i,k) 表示，从位置 i 走到位置 k 所需要的步数。

虽然这样子的时间复杂度是 O(nm)，但是由于还要加上进栈和退栈的时间，所以可能常数比较大，无法通过此题，只能得到 85 分。所以我们就要考虑优化常数。我们可以发现上述过程可以只用一个变量来统计，对于每一个即将进栈的数，我们直接比大小就行了，于是就可以通过此题了。

代码部分：

// dp数组用滚动数组优化内存
//如果无法到达，就用无穷大来代替这个状态
//minx就是充当单调栈的作用
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+1,M=1e5+1;
int n,m,L,dp[2][N],tot,ans;
char s[N],t[M];
signed main()
{
    scanf("%lld%lld%lld\n%s\n%s",&n,&m,&L,s+1,t+1);
    for(register int i=1;i<=m;i++)
    {
        int tott=tot^1,mini=1ll<<31,minx=1ll<<31;
        memset(dp[tott],127/3,sizeof(dp[tott]));
        for(int j=1;j<=n;j++)
        {
            minx=min(minx,dp[tot][j]);
            if(s[j]==t[i])
            {
                dp[tott][j]=min(dp[tott][j],minx);
                mini=min(mini,dp[tott][j]);
            }
            minx++;
        }
        for(int j=n;j>=1;j--)
        {
            minx=min(minx,dp[tot][j]);
            if(s[j]==t[i])
            {
                dp[tott][j]=min(dp[tott][j],minx);
                mini=min(mini,dp[tott][j]);
            }
            minx++;
        }
        tot=tott;
        if(mini<=L) ans=i;
        else break;
    }
    printf("%lld",ans);
    return 0;
}

如有更优做法，欢迎提供。