CF2011C Split the Expression

给定一个字符串 $s$，其形式为“数字块+数字块+...+数字块”。每个数字块由至少 $2$ 位、至多 $13$ 位数字组成，每位数字均为 $1$ 到 $9$。 你需要将该字符串划分为若干个形如“整数+整数”的表达式。每个表达式必须是原字符串的连续子串，并且原字符串中的每个字符恰好属于一个表达式。例如，若字符串为 123+456+789+555，则： - 你可以将其划分为 123+4、56+7 和 89+555； - 你不能划分为 123+456 和 +789+555，因为第二部分以加号开头； - 你不能划分为 123+4、56+7、8 和 9+555，因为第三部分不包含加号； - 你不能划分为 123+456+78 和 9+555，因为第一部分包含了两个加号。 在所有合法的划分方式中，找出一种使所有表达式结果之和最大的划分方式，并输出该最大和。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 每个测试用例包含一行字符串 $s$（$5 \le |s| \le 1000$），其形式为“数字块+数字块+...+数字块”。字符串中至少包含一个加号。每个数字块由至少 $2$ 位、至多 $13$ 位数字组成，每位数字均为 $1$ 到 $9$。

对于每个测试用例，输出一个整数，表示将字符串划分后所有表达式结果的最大可能和。

在第一个样例中，应将字符串划分为表达式 123+4、56+7 和 89+555。这些表达式的结果之和为 $834$。 在第二个样例中，给定的字符串已经是一个合法表达式，无法进一步划分。 由 ChatGPT 4.1 翻译