题目大意
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1< k< =40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
思路
#include#include #include #include #include using namespace std;const int MAX_LEN = 210, MAX_K = 45, MAX_WORD_CNT = 10, MINF = 0xcfcfcfcf;int W[MAX_LEN][MAX_LEN], F[MAX_LEN][MAX_K];string S, P[MAX_WORD_CNT];int PCnt, K;void Read(){ int lineCnt; cin >> lineCnt >> K; string temp; for (int i = 0; i < lineCnt; i++) { cin >> temp; S += temp; } cin >> PCnt; for (int i = 0; i < PCnt; i++) cin >> P[i];}void GetW(){ for (int j = 0; j < S.length(); j++) for (int i = j; i >= 0; i--) { int prevVal = i == j ? 0 : W[i + 1][j]; W[i][j] = prevVal; for (int p = 0; p < PCnt; p++) if (j - i + 1 >= P[p].length() && S.substr(i, P[p].length()) == P[p]) W[i][j] = prevVal + 1; }}int GetAns(){ memset(F, MINF, sizeof(F)); for (int i = 0; i < S.length(); i++) F[i][1] = W[0][i]; for (int i = 0; i < S.length(); i++) for (int k = 2; k <= K; k++) for (int l = 0; l < i; l++) F[i][k] = max(F[i][k], F[l][k - 1] + W[l + 1][i]); return F[S.length() - 1][K];}int main(){ Read(); GetW(); printf("%d\n", GetAns()); return 0;}