CF1461F Mathematical Expression 题解

· · 题解

稍微分讨一下：+、-、*、+-、*- 都是简单的，这里不再赘述。

*+ 和 *+- 是等价的，因为把所有 - 换成 + 不会变劣，所以只用考虑 *+ 的情况。

考虑填完 * 和 + 后结果是如何计算的，发现就是所有 * 连续段每段积的和。

那就是要你把原序列划分成若干个子段，要你最大化每段乘积的和。

0 对乘法是特殊的，如果其被包含在 * 连续段中必然不优，其一定是单独的一个子段。

所以相邻的两个 0 间的符号填写就变成了若干个独立的子问题，并且这些子问题的序列中不存在 0。

后文中用 m 表示子问题的大小。

1 对于乘法也是较为特殊的，如果没有 1 那一定是全部乘起来最大。

有个显然的性质，如果一个连续段中存在 1 的前缀或是后缀，那把那个前缀或者后缀单独拉出来变成一个连续段一定更优。

考虑虽然有 1，但符号填写大体上还是填 * 较优，因此我们考虑把两个相邻的子段合并起来对答案贡献的影响。

假设两个连续段乘积分别为 a 和 b，\Delta=a\cdot b-a-b=(a-1)(b-1)-1。

显然如果 a>1 且 b>1，那把 a 和 b 合并就是不劣的，所以相邻的非 1 子段合并起来一定不劣。

同时显然 1 的子段必然单独存在。

那么所有不劣的划分方式一定是：先将所有非 1 连续段合并，因为最后它们一定在同一子段内，然后再将这些非 1 连续子段拼成若干子段（合并的时候中间可能夹了一些 1），然后 1 以单独子段的形式夹在非 1 子段中间。比如这就是一个例子：1+1+8*9*1*1*3*2*1*1*7*3+1+1+5*3*1*1*2+1。

那我们继续考虑将两个中间夹了 l 个 1 的非 1 子段合并起来对答案的影响。

这个东西可以看成先有 a\cdot b-a-b 的增量，然后有 l 的减量，注意到如果 a 和 b 的乘积大于 2m+\Theta(1)，那无论中间有多少个 1，将其合并一定不劣。

更进一步的，我们发现把若干个非 1 子段合并一定比两个非 1 子段合并对答案的贡献的增量更大（具体为 \prod a_i-\sum a_i \ge a_1\cdot \prod _{i=2}a_i-a_1-\prod_{i=2}a_i），而合并之后答案的减量仍然不超过 m。

所以如果当前局面上所有非 1 子段的乘积大于 2m+\Theta(1)，那把它们全部合并一定是不劣。

也就是说，如果初始序列上所有非 1 值的乘积大于 2m+\Theta(1)，那把它们全部合并到一个子段里一定是最优（不劣）解。

而如果所有非 1 值乘积小于 2m+\Theta(1)，那它们的个数一定小于 \log_{2}m+\Theta(1)。

那非 1 子段的拼接直接 2^{size} 暴捜就可以做到时间复杂度 \Theta(m)。

所以总时间复杂度 \Theta(n)。