数学表达式：题解

思路

乘号会把连续数字合成一个乘积块，加号或减号把相邻乘积块连接起来。小规模可以枚举全部运算符；中等规模可以枚举最后一个乘积块；满分则利用数字只有 $0$ 到 $9$ 的性质分类构造。

做法

子任务 1：枚举

枚举 $n-1$ 个位置选择的运算符，按乘法优先级用任意精度整数计算表达式，保留最大值对应的方案。

子任务 2：乘积块动态规划

令 $f_r$ 为使用前 $r$ 个数字能得到的最大值。枚举最后一个乘积块的左端点 $l$，计算 $a_l\cdots a_r$；若 $l=1$，它就是整个表达式，否则枚举允许的 + 或 - 与 $f_{l-1}$ 连接。记录前驱即可还原表达式。

满分算法

• 有 + 和 * 时，减号没有必要使用，且 $0$ 两侧一定可以放 +。对每个不含 $0$ 的段，把连续的非 $1$ 数字压成乘积块，块间只剩若干个 $1$。若所有块乘积达到 $10^9$，整段核心全部相乘必然优于任何切分；否则大于 $1$ 的因子不超过 $O(\log 10^9)$ 个，对压缩后的块做平方级划分 DP，决定哪些块之间放 +。
• 只有 + 而没有 * 时，全部放 +。
• 同时有 - 和 *、但没有 + 时：若第一个 $0$ 不在首位，就在它之前放一个 -，其余全部放 *，得到“前缀乘积减去零”；若没有 $0$ 或首项为 $0$，全部放 *。
• 剩余情形只有一种有用的运算符，全部使用它。

这些规则逐块比较乘积与和即可证明最优；$0$ 和 $1$ 是乘法块的唯一特殊点，而不含加号时第一个零能把所有后缀代价乘成零。

复杂度

枚举算法为 $O(|s|^{n-1}n)$；乘积块动态规划为 $O(n^2)$；满分算法中压缩块数不超过 $O(\log 10^9)$，总时间为 $O(n+\log^2 10^9)$，空间为 $O(n)$。