Bzoj 1633(字符串DP)

BZOJ 1633
Luogu 2875
from: USACO 2007 Jan Sliver(USACO刷题第13题)

刚开始根本没想到DP,什么kmp,AC自动机,后缀数组都想了。。看了题解才知道
解决字符串的几大武器:(字符串DP,字符串Hash,KMP,AC自动机,后缀家族……)

本题设$f[i]$为给定串前$i$个字符进行处理后最少删除的字符数。
刚开始想了个超时的方法。。然后发现其实直接写就行了。。还是太弱
方程:$$f[i] = min(f[i], f[k]+cnt)$$
其中$k$满足$[k,i]$之间能够被字典中的词匹配(可以删字符),$cnt$为为此删除的字符数
初始化$f[i] = 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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXW = 600 + 5, MAXL = 300 + 5;
char dic[MAXW][MAXL], s[MAXL];
int n, L, f[MAXL];
void clear() {}
void init() {
clear();
scanf("%s", s+1);
for (int i=1;i<=n;i++) scanf("%s", dic[i]+1);
}
void solve() {
for (int i=1;i<=L;i++) {
f[i] = i;
for (int j=1;j<=n;j++) {
int len = strlen(dic[j]+1);
int k, cnt = 0;
for (k=i;k>0;k--) {
if (dic[j][len]==s[k]) len--; else cnt++;
if (len==0) break;
}
if (len==0) f[i] = min(f[i], f[k-1]+cnt);
}
}
printf("%d\n", f[L]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n ,&L)==2) init(), solve();
return 0;
}

------ 本文结束 ------