【codevs 1040】 1040 统计单词个数 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。 要求将此字母串分成k份，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以算做包含2个is）。 （1 < k <= 40) 单词在给出的一个不超过6个单词的字典中。 要求输出最大的个数。
输入描述 Input Description 第一行为一个正整数表示有n组测试数据 (0 < n <= 5) 每组的第一行有二个正整数(p，k) p表示字串的行数; k表示分为k个部分。 接下来的p行，每行均有20个字符。 再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6) 接下来的s行，每行均有一个单词。
输出描述 Output Description 每行一个整数，分别对应每组测试数据的相应结果。
样例输入 Sample Input 1 1 3 thisisabookyouareaoh 4 is a ok sab
样例输出 Sample Output 7
数据范围及提示 Data Size & Hint this/isabookyoua/reaoh
每个区间有一个最优值 分求最后合并
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 205; int fa[MAXN][MAXN];//fa[i][j]区间[i,j]中的单词数 int dp[MAXN][MAXN];//前i个字符分成j份的最优解 string word,word2[10],xc; int sk,ss; int n,q; void work() { // bool flag; int flag; memset(fa,0,sizeof(fa)); int len = word.length(); for(int i = len - 1; i >= 0; i --) { for(int j = i; j >= 0; j --) { for(int k = 0; k < ss; k ++) { // flag = false; flag = 0; if(word.find(word2[k],j) == j) if(word2[k].size() <= i - j + 1)// word2要有明确大小QAQ // flag = true; flag = 1; if(flag) break;//有单词可以匹配 } fa[j][i] = fa[j + 1][i] + flag;//╮(╯_╰)╭ } } } void dpdpd() { memset(dp,0,sizeof(dp)); int len = word.length(); for(int i = 0; i < len; i ++) dp[i][1] = fa[0][i]; for(int k = 2; k <= sk; k ++)// for(int i = k - 1; i < len; i ++) for(int j = i - 1; j >= k - 1; j --) dp[i][k] = max(dp[i][k],dp[j][k - 1] + fa[j + 1][i]); } int main() { scanf("%d",&n); for(int i = 1; i <= n; i ++) { scanf("%d %d",&q,&sk); word.clear(); for(int j = 1; j <= q; j ++) { cin >> xc; word += xc;//字符串优势 } scanf("%d",&ss); for(int i = 0; i < ss; i ++) cin >> word2[i]; work(); dpdpd(); int lens = word.length(); printf("%d\n",dp[lens - 1][sk]); } return 0; }