题解 - P12129 [蓝桥杯 2024 省 B 第二场] 遗迹（加强版）
xh2407lr
·
·
题解
考虑 DP。
设 $t$ 中需要输入的下一个字符的位置为 $x$ ，有转移 $f_{i,j+|x-k|,x} ← f_{i,j,k}$ 。
不难发现 $f_{i,j,k}$ 的取值只与当前位是否被转移过有关，也就是说原来的 true 和 false 的位置可以塞一个状态进去。
设状态为 $f_{i,j}$ 入到字符串 $t$ 的第 $i$ 位，当前指针位置为 $j$ 时，$f_{i,j}$ 为指针移动距离 $l$ 的最小值。
设 $t$ 中需要输入的下一个字符的位置为 $k$ ，有转移 $f_{i+1,k} ← f_{i,j}+|j-k|$ 。
此时时间复杂度为 $O(m\cdot n^2)$ ，无法通过本题，需要优化时间复杂度。
DP 的时间复杂度是状态数量和转移复杂度的乘积，当前状态数量无法优化，只能优化转移。
转移可以拆分成两种情况：
（1）若 $j\le k$ 转移方程变为 $f_{i+1,k} ← f_{i,j}-j+k$。
（2）若 $j>k$ 转移方程变为 $f_{i+1,k} ← f_{i,j}+j-k$。
我们可以分别维护两个数组：
（1）$pre_j$ 表示 $f_{i,j}-j$ 的前缀最小值。
（2）$suf_j$ 表示 $f_{i,j}+j$ 的前缀最大值。
此时的转移为：
$$
f_{i+1,j}← \min(pre_j+k,suf_{j+1}-k)
$$
若没有合法的 $f_{i,j}$ 能够转移到 $f_{i+1,k}$ ，那么当前的 $i$ 就是答案。
此时代码时间复杂度 $O(mn)$，可以通过本题。
若本题的空间限制为 256 MB，则需要考虑滚动数组优化，但是这道题有 512 MB，空间足够。
::::success[参考代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1e5+10;
int n,m,l;
int pre[N],suf[N],f[M][N],ans;
char s[N],t[M];
int main()
{
cin>>n>>m>>l;
cin>>s+1>>t+1;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
f[0][i]=0;
pre[0]=0x3f3f3f3f,suf[n+1]=0x3f3f3f3f;
for(int i=0;i<m;i++)
{
for(int j=1;j<=n;j++)
pre[j]=min(f[i][j]-j,pre[j-1]);
for(int j=n;j>=1;j--)
suf[j]=min(f[i][j]+j,suf[j+1]);
for(int k=1;k<=n;k++)
if(s[k]==t[i+1])
{
f[i+1][k]=min(f[i+1][k],min(suf[k+1]-k,pre[k]+k));
if(f[i+1][k]<=l)
ans=i+1;
}
}
cout<<ans;
return 0;
}
```
::::