1 条题解
-
0
题目分析
内层的括号会产生大于 的数,因此现在考虑由任意正整数构成的数列如何插入 。
考虑两个相邻的数 ,如果 ,那么断言 之间必插入乘号。这是因为不管 左边和 右边是什么情况,所造成影响只会是 乘系数 , 乘系数 (),于是仍然有 ,也就是说 之间仍应该放乘号而非加号。
同理我们可以推广到多个数 ,如果连乘已经是这 个数的局部最优,那么一定也是全局最优。
因此,对于一个正整数列 ,我们的处理办法就是从小到大枚举区间长度,再枚举这个长度的区间(类似区间 DP),看看这个区间的乘积是否大于加和,如果更大,则直接乘起来合并为一个数,然后继续上述过程。最终就得到了 可以算出的最大结果。
这个算法的正确性是比较显然的:由于我们从小到大枚举区间长度,因此对于已经枚举过的区间,倘若没有合并,则说明全加是最优的,那么假设当前一个数列 的最优解有 ,若不是全设为 ,则一定形如 $a_1\times\dots\times a_t+a_{t+1}\times\dots\times a_p+\dots$,但 的最优方案是全 ,因此矛盾,于是只能是全 ,所以我们只需要比较全 和全 即可确定最优解;而依据开始的分析,如果是全 则可以直接合并。至此,我们说明了算法的正确性。
从小到大枚举区间这件事可以通过从小到大枚举右端点 ,再从大到小枚举左端点 实现,这个过程与处理中缀表达式的栈是类似的,因此可以放一起处理,只不过枚举的 到了最近的
(就应当停止。原序列的任意一个区间只会被枚举到一次,因此总复杂度 。
需要注意过程中可能得到较大的数,但实际上只要某个数大于了 ,那它与相邻的数(除非是一列 )必然是相乘优于相加,所以我们只需要记录每个数对 取模的值,以及它的实际值是否已经大于 即可。
- 1
信息
- ID
- 185
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者