原题链接
题目描述
给定$n$个长度不超过10的字符串以及$m$次询问，每次询问会给定一个操作次数上限。求每次询问小于等于操作次数上限，能够让给定的字符串变为询问字符串的个数。
一次操作意味着修改一个字符，删除一个字符，以及加入一个字符。
直接暴力求解即可，时间复杂度为$O(mnL^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
30
31
32
33
| #include <bits/stdc++.h>
using namespace std;
int n, m, limit;
const int N = 1010;
char s[N][13];
char tmp[13];
int f[N][N];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%s", &s[i][1]);
while(m--) {
scanf("%s%d", tmp+1, &limit);
int cnt = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= strlen(&s[i][1]); ++j)
f[0][j] = j;
for(int j = 1; j <= strlen(tmp+1); ++j)
f[j][0] = j;
for(int k = 1; k <= strlen(tmp+1); ++k) {
for(int j = 1; j <= strlen(&s[i][1]); ++j) {
if(s[i][j] == tmp[k]) f[k][j] = f[k-1][j-1];
else {
f[k][j] = min(f[k-1][j-1], min(f[k-1][j], f[k][j-1]))+1;
}
}
}
if(f[strlen(tmp+1)][strlen(&s[i][1])] <= limit) cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
|
注意，在这里memset是不必要的，加了甚至会TLE…
