详细题解

一、问题转化 给定字符串 $s$ 由数字块和 '+' 组成，形式为 $D_1$+$D_2$+...+$D_m$，其中每个 $D_i$ 是长度在 $2$ 到 $13$ 之间的数字串，且只包含数字 $1$∼$9$。 我们需要将 $s$ 分割成若干个形如 $A$+$B$ 的表达式，每个表达式是原串的连续子串且恰好包含一个 '+'，并且整条 $s$ 的每个字符恰好属于一个表达式。 显然，表达式个数必须等于原串中 '+' 的个数，即 $m-1$ 个。

二、分割的唯一结构 为了保证字符串恰好被覆盖，分割方式必然具有以下结构：

• 第一个表达式以完整的 $D_1$ 作为左操作数，右操作数是 $D_2$ 的一个非空前缀。
• 最后一个表达式以完整的 $D_m$ 作为右操作数，左操作数是 $D_{m-1}$ 的一个非空后缀。
• 对于中间的每一个数字块 $D_i$ ($i$ 从 $2$ 到 $m-1$)，它会被切成两个非空部分：前缀 $pre_i$ 和后缀 $suf_i$。 其中 $pre_i$ 作为第 $i-1$ 个表达式的右操作数，$suf_i$ 作为第 $i$ 个表达式的左操作数。

下图展示了对 $m=4$ 时的分割结构（以 $123+456+789+555$ 为例）： 表达式1： $D_1$ + $pre_2$ → 123 + 4 表达式2： $suf_2$ + $pre_3$ → 56 + 7 表达式3： $suf_3$ + $D_4$ → 89 + 555 其中 $D_2$="456" 被切成 $pre_2$="4" 和 $suf_2$="56"， $D_3$="789" 被切成 $pre_3$="7" 和 $suf_3$="89"。

三、总和表达式 设 $val(X)$ 表示数字串 $X$ 的十进制数值。那么所有表达式结果的总和为：

$$\text{ans} = val(D_1) + val(D_m) + \sum_{i=2}^{m-1} \big(val(pre_i) + val(suf_i)\big) $$

并且对于每个 $i$，$pre_i$ 与 $suf_i$ 的拼接等于 $D_i$，即 $pre_i + suf_i = D_i$（字符串拼接）。

四、贪心策略 注意到上式中的每一项 $val(pre_i) + val(suf_i)$ 只与 $D_i$ 的分割点有关，不同 $D_i$ 之间互不影响。因此，要最大化总和，我们只需要对每一个中间块 $D_i$ 独立地选择切割点，使得 $val(pre) + val(suf)$ 最大。这种局部的贪心选择可以得到全局最优解。

五、算法步骤

1. 读取字符串 $s$，按 '+' 分割得到数字块列表 $D_1, D_2, \dots, D_m$。
2. 如果 $m = 2$（即原串只有一个 '+'），则无法再做分割，答案直接为 $val(D_1) + val(D_2)$。
3. 初始化 $ans = val(D_1) + val(D_m)$。
4. 对于 $i$ 从 $2$ 到 $m-1$：
   • 令当前块字符串为 $t$，长度为 $L$。
   • 枚举切割点 $j$ 从 $1$ 到 $L-1$，计算前缀数值 $pre = val(t[0..j-1])$，后缀数值 $suf = val(t[j..L-1])$。
   • 记录 $pre + suf$ 的最大值。
   • 将最大值累加到 $ans$ 中。
5. 输出 $ans$。

六、示例演示 输入：$123+456+789+555$ 数字块： $D_1$="123", $D_2$="456", $D_3$="789", $D_4$="555" $val(D_1)=123$, $val(D_4)=555$ 中间块 $D_2$="456"： $j=1$ → $4 + 56 = 60$ $j=2$ → $45 + 6 = 51$ 最大为 $60$ 中间块 $D_3$="789"： $j=1$ → $7 + 89 = 96$ $j=2$ → $78 + 9 = 87$ 最大为 $96$ 总和 $ans = 123 + 555 + 60 + 96 = 834$。输出 $834$。

七、复杂度分析 每个数字块的长度不超过 $13$，枚举切割点的次数为 $O(L)$（常数级）。总共有 $m \le |s|/3$ 个块，整体时间复杂度为 $O(|s|)$，可以处理 $t \le 100$，$|s| \le 1000$ 的数据。

八、正确性证明 任何合法的分割方案必然具有上述结构，因为字符串必须恰好被不重叠的表达式覆盖，且每个表达式恰好含一个 '+'。第一个 '+' 左侧部分必须完整属于第一个数字块，否则会出现孤立数字。类似地可推出所有块的切分方式。总和表达式中的交叉项相互独立，因此全局最大值等于各独立部分最大值之和，贪心策略正确。