解题思路

本题要求把一段不含空格的小写英文字符串切分为若干“词元”，并最大化： 所有词元的置信度分数之和 + 相邻词元之间的转移加分之和。 若无法完全用词表中的词覆盖整句，则输出 0。

核心算法：动态规划（DP）

• 设原串为 text，长度为 L。
• 用哈希表保存词表 score[w]（词 w 的置信度分数）与转移加分 bonus[u][v]（从词 u 到 v 的转移分）。

题目内容

您正在为一种罕见的语言构建一个专用的大语言模型。由于训练样本缺失，传统$BPE$等标准的分词器效果不佳，使得大模型推理生成的句子不理想。

幸运的是，一位语言学家为罕见的语言的已知词根和词缀(我们统称为“词元"或“$Token$”)都标注了一个“置信度”分数，这个分数代表了该词元作为一个“独立单位”的合理性，同时，语言学家还总结出了一个转移分数表，表示当前词元选择对下一个词元"置信度"的影响。

您的任务是设计并实现一个“最优分词器”，它能将输入的罕见语言句子(一个不含空格的英文小写字符多也串)切分成一系列词元，并使得所有词元的置信度分数之和达到最大，从而帮助大语言模型在后续处理中能够输出更合理的句了

输入描述

第一行输入待分词的字符串 $text$，假设只包含英文小写字母；

接着输入词典词条数 $n$；

然后输入$n$行，每一行包含一个单词和对应的分值，以空格分隔。

第 $n+3$ 行为转移分数的个数 $m$。

随后$m$行为转移分数数据。包括起始词、下一个词、转移分数加分$X$。以空格分隔。

参数范围说明：

1. $0 < len(text) \leq 100$
2. $-100 \leq$ 词典中单词的得分 $\leq 100$
3. $-100 \le$ 词汇表置信度分数$P \le 100$
4. 输入的字符串都是英文小写字母
5. $0 <$词汇表大小 $n \le 100$

输出描述

返回最高的分词得分，若根据已知间汇表无法拆分则返回$0$、我们约定若切分成一系列词元中含有不在已知词汇表中的词，则最终得分为$0$。

样例1

输入

applepie
2
pen 3
apple 10
2
pen apple 5
pie apple 2

输出

0

说明

$text$中的字符不能和词典词条匹配出切分结果，无法计算得分。

样例2

输入

goodeats
4
good 15
goo 12
deats 14
eats 10
1
good eats -5

输出

26

说明

切分为["$good$","$eats$"] 的总分$= 15 + 10 - 5 = 20$；

切分为 ["$goo$","$deats$"] 的总分$= 12 + 14 = 26$；

所以最大得分为 $26$。