统计单词个数

发表于 更新于 分类于

Problem’s Website

  • 统计单词个数

    Solution

  • 这是一道关于字符串和dp的题目

  • 首先要把题意读明白，下面是样例解释

    1
    2
    3
    4
    5
    6
    7
    8
    this/isabookyoua/reaoh
    1:is(this)
    2:is(isabookyoua)
    3:sab(isabookyoua)
    4:a(isabookyoua)
    5:ok(isabookyoua)
    6:a(isabookyoua)
    7:a(reaoh)

  • 题意搞懂后，我们来想正解，本题的状态不难想出，设f[i][j]为长度为i的字符串分成j块包含的单词个数，答案为f[len][k]，经过思考，发现状态转移只有一个f数组还不够，于是我们再维护一个sum数组，sum[i][j]表示从i到j的单词个数，维护这个数组需要用到STL：string类型的find()函数和substr()函数，不懂的可以点击对应名称进行学习。状态转移比较好理解，枚举字符串长度和分割的块数，然后枚举断点，方程为

    1
    f[i][j] = max(f[i][j], f[l][j - 1] + sum[l + 1][i];

Code

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
int sc() {
	int xx = 0, ff = 1; char cch = gc;
	while (cch < '0' || cch > '9') {
		if (cch == '-') ff = -1; cch = gc;
	}
	while (cch >= '0' && cch <= '9') {
		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
	}
	return xx * ff;
}
string s;
int n, k, m, len;
int f[210][50], sum[210][210];
string a[10];
bool check(int l, int r) {
	string x = s.substr(l, r - l + 1);
	for(int i = 1; i <= m; i++)
		if(x.find(a[i]) == 0) return true;
	return false;
}
int main() {
	n = sc(); k = sc();
	s += '~';
	for(int i = 1; i <= n; i++) {
		string ch;
		cin >> ch;
		s += ch;
	}
	len = s.size() - 1;
	m = sc();
	for(int i = 1; i <= m; i++)
		cin >> a[i];
	for(int i = len; i >= 1; i--) {
		for(int j = i; j >= 1; j--) {
			sum[j][i] = sum[j + 1][i];
			if(check(j, i))
				sum[j][i]++;
		}
	}
	for(int i = 1; i <= k; i++)
		f[i][i] = f[i - 1][i - 1] + sum[i][i];
	for(int i = 1; i <= len; i++)
		f[i][1] = sum[1][i];
	for(int i = 1; i <= len; i++) {
		for(int j = 1; j < i && j <= k; j++)
			for(int l = j; l < i; l++)
				f[i][j] = max(f[i][j], f[l][j - 1] + sum[l + 1][i]);
	}
	printf("%d\n", f[len][k]);
 	return 0;
}

rp++