【NOIP2001】【LuoguP1026】统计单词个数
题目链接: https://www.luogu.org/problem/P1026
前言
这题要不是有DP标签我还真想不出这种思路。
分析
首先题目描述有点不清楚，结合样例更加好理解。差不多为，字符串长度不超过200，单词种类不超过6个，将字符串分40段求最大单词匹配总数。
然后给出了一个性质，一个字符自能被当做一次首字符，所以就可以用线性做法。
我们先预处理，求出每个单词在字符串中的所有匹配位置。那么如果几个单词重叠了该怎么办呢？
很容易想到，字符串中某字符被当做首字母时，匹配最短的单词最优。因此我们可以求出字符串中每一个字符当首字母时的最短长度。
如果使用string可以使用find函数，但输入时较为麻烦。所以我用char数组存储，并使用strstr函数。
接下来考虑DP方程。（因为有DP标签，才会拼凑DP思路，考场上还真不一定想出DP解法）
非常典型的设一个$F[N][K]$，表示处理到第N个字符，分割为K部分。
先上经典转移方程进行修改。
$$F[i][j] = max(F[i - 1][j], f[i - 1][j - 1])$$
但你会发现这样没地方加入预处理出的最短长度。因为后面转移时，单词有可能从中间被切开，这样求出答案就是错了。
然后就写了个鬼畜的方程，设$W_i$为字符串中第i字符当首字母时最短长度（如果不能匹配则无限大）。
所以$i$会影响到$i + W_i$后的答案，使他们答案+1，取个max。
然后我们以j为第一关键字，i为第二关键字枚举即可。因为我们分隔字符只会让答案变小，所以将方程改为。
$$F[i][j] = max(F[i][j], f[i - 1][j - 1])$$
代码
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
| #include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int p, k, s, w[405], len[7], a[405], f[205][45];
char tmps[405], zd[7][205];
int main() {
cin >> p >> k;
for(int i= 0; i < p; i++) cin >> (tmps + i * 20 + 1);
p*= 20;
memset(w, 0x3f, sizeof(w));
cin >> s;
for(int i= 1; i <= s; i++) {
cin >> zd[i], len[i]= strlen(zd[i]);
char *st= strstr(tmps + 1, zd[i]);
while(st) {
w[st - tmps]= min(w[st - tmps], len[i]);
st= strstr(st + 1, zd[i]);
}
}
for(int l= 1; l <= k; l++) {
for(int i= l; i <= p; i++) {
f[i][l]= max(f[i][l], f[i - 1][l - 1]);
if(w[i] != 0x3f3f3f3f) {
for(int j= max(i + w[i] - 1, i + 1); j <= p; j++) f[j][l]= max(f[j][l], f[i][l]) + 1;
if(w[i] == 1) ++f[i][l];
}
}
}
cout << f[p][k] << endl;
return 0;
}
|
