NOIP2001统计单词个数

题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1< k< =40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。

输入

第一行有二个正整数(p，k)

p表示字串的行数; k表示分为k个部分。

接下来的p行，每行均有20个字符。

再接下来有一个正整数s，表示字典中单词个数。(1< =s< =6)

接下来的s行，每行均有一个单词。

输出

输出一个整数，即最大的个数

样例输入

1 3
thisisabookyouareaoh
4
is
a
ok
sab

样例输出

7

分析

这道题是一道很明显的区间dp
记 $f\left[i\right]\left[k\right]$f[i][k]表示前 $i$i个字母分成 $k$k份的最大单词个数， $hav\left[i\right]\left[j\right]$hav[i][j]表示从 $i$i到 $j$j这段区间包含的单词个数
转移方程：
$f\left[i\right]\left[k\right]=max\left(f\right[j\left]\right[k-1]+hav[i\left]\right[j\left]\right)$f[i][k]=max(f[j][k−1]+hav[i][j])
$hav\left[i\right]\left[j\right]$hav[i][j]怎么得到？题目要求的是包含首字母的只能有一个，于是我们就倒推：
$hav\left[i\right]\left[j\right]=hav[i+1]\left[j\right]$hav[i][j]=hav[i+1][j]， 如果区间内有以i开头的单词， $hav\left[i\right]\left[j\right]$hav[i][j]++（加一次就可以了）

代码如下

//f[i][k] = max(f[j][k-1] + hav[i][j])
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[205][205], hav[205][205], len, c;
char v[25], w[25][25], s[205];
int ok(int x, int p, int l){
	int i;
	for(i = 1; i <= l; i++){
		if(w[p][i] != s[x + i - 1]) return 0;
	}
	return 1;
}
int main(){
	int i, j, k, t, n, m;
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	len = 20;
	for(i = 2; i <= n; i++){
		scanf("%s", v);
		for(j = 0; j < 20; j++) s[++len] = v[j];
	}
	//printf("%s", s);
	scanf("%d", &m);
	for(i = 1; i <= m; i++) scanf("%s", w[i] + 1);
	for(i = len; i >= 1; i--){
		for(j = i; j <= len; j++){
			hav[i][j] = hav[i+1][j];
			for(t = 1; t <= m; t++){
				c = strlen(w[t] + 1);
				if(i + c - 1 <= j && ok(i, t, c)){
					hav[i][j]++;
					break;
				}
			}
			//printf("===%d %d %d\n", i, j, hav[i][j]);
		}
	}
	for(i = 1; i <= len; i++){
		for(t = 1; t <= min(i, k); t++){
			for(j = t-1; j < i; j++){
				f[i][t] = max(f[i][t], f[j][t-1] + hav[j+1][i]);
			}
		}
	}
	printf("%d", f[len][k]);
	return 0;
}