题目大意：S串最少修改多少次可以匹配T串（子序列）
如果是匹配子串，那就是个贪心了，但是匹配子序列，肯定是dp
类似匹配dp
状态：设\(f_{ij}\)表示S串中前i个字符修改j次最长可以匹配的序列（第二维即时答案）
初始：都是0
转移：\(f_{i,j}=max(f_{i-1,j}+(s_i==t_{f_{i-1,j}+1}),f_{i-1,j-1}+1)\)
简单来说，就是对于第i位，考虑当前是否替换
\(f_{i-1,j}+(s_i==t_{f_{i-1,j}+1})\)即为不替换当前
\(f_{i-1,j-1}+1\)即为替换当前（不考虑当前的情况，直接暴力从原来的基础上加1）
时空复杂度都为：\(O(n^2)\)
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 66;
int n, m, res = 123456789;
char s[N], t[N];
int f[N][N];
signed main()
{
int i, j;
scanf ("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1);
for (i = 1; i <= n; ++ i)
{
for (j = 0; j <= i; ++ j)
{
f[i][j] = f[i - 1][j] + (s[i] == t[f[i - 1][j] + 1]);
if (j) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
f[i][j] == m ? res = min(res, j) : res = res;
}
}
printf ("%d", res);
return 0;
}
|
咦？我们观察发现第一维度好想可以滚掉
虽然此题没卡空间，但是如果卡的话….
滚动数组：开个变量now记录当前是0还是1
然后来回倒腾，在0的时候用1来转移，在1的时候用0来转移
空间复杂度：\(O(N)\)
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 66;
int n, m, res = 123456789;
char s[N], t[N];
int f[2][N];
signed main()
{
int i, j, now(0);
scanf ("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1);
for (i = 1; i <= n; ++ i)
{
for (j = 0; j <= i; ++ j)
{
f[now][j] = f[now ^ 1][j] + (s[i] == t[f[now ^ 1][j] + 1]);
if (j) f[now][j] = max(f[now][j], f[now ^ 1][j - 1] + 1);
f[now][j] == m ? res = min(res, j) : res = res;
}
now ^= 1;
}
printf ("%d", res);
return 0;
}
|
后记：
此题不难，状态很多种
A了之后去看题解，发现状态跟我设的都不一样
我觉得我的状态貌似难理解一点，我要是设一个主流的状态，或许会更快的做出来这道题