考虑动态规划的作法，设 $dp[i]$ 表示原字符串的前 $i$ 位最少需要删除的字符的数量，显然最后的答案是 $dp[L]$。
对于初始值，因为求最小值，所以先把 $dp[i]$ 均设置为 $+\infty$，同时由转移方程的含义可知 $dp[0] = 0$。然后就是处理单词与文章是否能匹配的核心思路了，设 $dx$ 表示当前匹配到的位置 $i$，$dy$ 表示第 $j$ 个单词的长度 $len[j]$。从 $i$ 与单词的末尾开始，若成功匹配，则 $dx,dy$ 均减一，否则 $dx$ 减一。如果 $dy$ 的值先变为 $0$ 或者 $dx,dy$ 同时变为 $0$，这说明该单词能够在原字符串中匹配；但是如果不能匹配，显然原字符串的第 $i$ 个位置需要被删除。
所以有状态转移方程 $dp[i] = \min (dp[i - 1] + 1,dp[dx] + (i - dx - len[j])$，显然此时的 $dx$ 表示在匹配之后 $dx$ 的值，而不是初始的 $dx = i$。
讲了这么多，再看着代码理解一下叭！
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 605;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,dlen[MAX],dp[MAX];
char str[MAX >> 1],cor[MAX][30];
int main ()
{
n = read ();m = read ();
scanf ("%s",str + 1);
for (int i = 1;i <= n;++i)
{
scanf ("%s",cor[i] + 1);
dlen[i] = strlen (cor[i] + 1);
}
init (dp);
dp[0] = 0;
for (int i = 1;i <= m;++i)
{
dp[i] = dp[i - 1] + 1;
for (int j = 1;j <= n;++j)
{
int dx = i,dy = dlen[j];
while (dx && dy)
{
if (str[dx] == cor[j][dy]) --dx,--dy;
else --dx;
}
if (!dy) dp[i] = min (dp[i],dp[dx] + (i - dx - dlen[j]));
}
}
printf ("%d\n",dp[m]);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
