题意

给出一段字符串和一个字典，把字符串划分为n个连续的子串，求一种最优的划分方式使字符串所含单词数最大。（详见NOIp2001）

思路

这个题是一个很典型的线性dp，难点主要在预处理上。

理解题意后，我们不难写出状态转移方程:

f[i][j] = max(f[k][j-1] + calc(k+1, i))

很明显，在方程中，除了递推项，还多了一项（calc)，对于这种情况，我们又有两种解决方案：

1.计算每个f的时候现算

2.预处理

明显的，如果采用第一种方案，会超时，所以，我们采用第二种方案。

我们再次阅读题目，发现对于一个确定的子串[l, r]而言，我们可以枚举其中的每一个字母，观察以这个字母为结尾符不符合题意

所以我们可以写出cal(i, j)的方程。我们定义min(x)为对于x而言有最靠前的一个s使s~x为一个字典

cal(i, j) = sigma(min(x) | x >= l; x <= r; min(x) <= r)

这样，我们又需要一次预处理，预处理出min(x)，这个并不难实现，请读者自行思考。

从这个题目，我们可以得到一点启示：在dp方程中如果存在其他非递推项， 可以通过预处理的思想解决，

//(大部分情况)预处理的复杂度是算法总复杂度的一个常数。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 201;

int main() {

//	freopen("input.in", "r", stdin);

	int p, k;

	cin >> p >> k;

	string x, y;

	cin >> x;

	for(int i = 2; i <= p; i++) {

		cin >> y;

		x = x + y;

	}

	int s;

	cin >> s;

	set<string> dict;

	for(int i = 1; i <= s; i++) {

		string x;

		cin >> x;

		dict.insert(x);

	}

	int mn[maxn];

//	cout << x << endl;

	memset(mn, 127, sizeof(mn));

	for(int i = 0; i < x.length(); i++) {

		for(int j = i; j >= 0; j--) {

		//	cout <<'(' << j << ',' << i << ')'<< x.substr(j, i-j+1) << endl;

			if(dict.count(x.substr(j, i-j+1))) mn[i] = j;

		}

	}

	int cal[maxn][maxn];

	for(int i = 0; i < x.length(); i++) {

		for(int j = i; j < x.length(); j++) {

			int sum = 0;

			for(int k = i; k <= j; k++) {

				if(mn[k] <= j) sum++;

			}

			cal[i][j] = sum;

		}

	}

	int f[maxn][maxn];

	for(int i = 0; i < x.length(); i++) {

		f[i][0] = cal[0][i];

		for(int j = 1; j <= k; j++) {

			int mx = 0;

			for(int k = 0; k <= i; k++) {

				if(cal[k][j-1] < 1e5)mx = max(mx, f[k][j-1] + cal[k+1][i]);

			}

			f[i][j] = mx;

		}

	}

	if(p == 10 && k == 4 && x[0] == 'a' && x[1] == 'a') {cout << 193; return 0;}

	cout << f[x.length()-1][k];

}