894A题解|894A Solution
静静
·
2023-01-15
·
via 静静的小窝
这是之前出的一道题，稍微进行了一些小修改。
题目链接:https://codeforces.com/contest/894/problem/A
最简单的方法就是搜索遍历所有的可能的排列情况，即枚举结果字符串的每一位在原字符串中的位置，故复杂度为$O(n^3)$，如果需要的匹配的字符串更长，那么复杂度更高。
随后可以发现目标字符串要完全符合要求，意即只要有一位不符合就一定不被计算，故可剪枝，只有当前面的字符串都符合要求的时候才继续遍历，常数可以进行优化为原来的$\frac{1}{26}$，但复杂度仍旧不变。
从前面的剪枝可以发现并不一定要遍历每种可能才可以，可以保存中间量直接相加即动态规划。
可以一维存储原字符串的下标，一维存目标字符串的下标，表示到目前为止符合的字符串数量，随后从前往后相加得最后得数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| for (int j = 0; j < 105; j++)
{
for (int i = 1; i < 5; i++)
{
dp[i][j] = 0;
}
dp[0][j]=1;
}
for (int j = 0; j < st.length(); j++)
{
for (int i = 0; i < 3; i++)
{
if (st[j] == base[i])
{
dp[i + 1][j + 1] = dp[i][j] + dp[i+1][j];
}
else
{
dp[i + 1][j + 1] = dp[i + 1][j];
}
}
|
最后输出dp[3][st.length()]作为答案。
可以注意到过程当中一直是dp[i]到dp[i+1]，说明实际并不需要这一维度，可以删去这一维度到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| for (int i = 1; i < 5; i++)
{
dp[i] = 0;
}
dp[0] = 1;
for (int j = 0; j < st.length(); j++)
{
for (int i = 0; i < 3; i++)
{
if (st[j] == base[i])
{
dp[i + 1] = dp[i] + dp[i + 1];
}
else
{
dp[i + 1] = dp[i + 1];
}
}
}
|
同时注意到else实际上什么都没有做，可以直接删去。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
