解题思路

错解

贪心：每次都移动至当前最近的对应方块上。

反例：

$s=$ abxac

$t=$ abac

贪心结果（下标） $0\to 1\to 0\to 4$，答案为 $5$。

正确结果（下标） $0\to 1\to 3\to 4$，答案为 $4$。

答案与逾期不符合，故贪心解法不正确。

正解

首先，我们注意到数据范围的最后一句话，数据保证随机，那么这样每个字符的数量约为 $\frac{n}{26}$。

当我们要在键盘串查找一种字符的位置时，$O(n)$ 遍历效率较低，可以考虑先将字符串进行预处理，将字符 a 的下标全部存入 $g[0]$，字符 b 的下标存入 $g[1]$，$\dots$

设 $f[x]$ 表示当前情况下，以 $s[x]$ 作为结尾字符，键盘指针指向 $x$，构成字符串的最小代价。例如，设键盘串为 $abcdef$，$f[3]$ 表示构成 $abcd$，且最终键盘指针指向 $3$ 的最小代价。

计算出字符串 abcc 所需要的步数时：

• 我们可以先计算构成 a 的所有最短步数，键盘串中一定存在 a，设其中一个为 a 的下标为 $x$，那么 $f[x]=0$，由于 $f$ 数组定义在全局，故此处在代码中不体现。
• 接下来计算构成 ab 的所有最短步数，由于我们已经计算出了构成 a 的所有最短步数，那么我们可以暴力枚举所有 a 的位置，与所有 b 的位置，假设其中一个 a 的位置为 $y$，其中一个 b 的位置为 $x$，那么 $f[x]=min(f[x],f[y]+abs(x-y))$。
• 计算所有构成 abc 的做法如上。
• 计算所有构成 abcc 的最短步数，由于 $t[3]=t[2]$，故本轮可跳过。

时间复杂度 $O(m(\frac{n}{26}{)}^2)$。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>using namespace std;const int N = 1e3 + 10, INF = 0x3f3f3f3f;int n, m, t;
string s, str;
vector<int> g[26];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m >> t >> s >> str;for (int i = 0; i < n; ++ i )g[s[i] - 'a'].push_back(i);for (int i = 1; i < m; ++ i ){int u = str[i] - 'a', last = str[i - 1] - 'a';if (u != last){int res = INF;bool find = false;for (auto x: g[u]){for (auto y: g[last])res = min(res, f[y] + abs(x - y));f[x] = res;if (f[x] <= t)find = true;}if (!find){cout << i << endl;return 0;}}}cout << m << endl;return 0;
}