1 条题解

  • 0
    @ 2026-11-15 20:48:24

    题目分析

    内层的括号会产生大于 11 的数,因此现在考虑由任意正整数构成的数列如何插入 +,×+,\times。

    考虑两个相邻的数 x,yx,y,如果 x×y≥x+yx\times y\ge x+y,那么断言 x,yx,y 之间必插入乘号。这是因为不管 xx 左边和 yy 右边是什么情况,所造成影响只会是 xx 乘系数 aa,yy 乘系数 bb(a,b≥1a,b\ge 1),于是仍然有 ax×by≥ab(x+y)≥ax+byax\times by\ge ab(x+y)\ge ax+by,也就是说 x,yx,y 之间仍应该放乘号而非加号。

    同理我们可以推广到多个数 a1,…,asa_1,\dots,a_s,如果连乘已经是这 ss 个数的局部最优,那么一定也是全局最优。

    因此,对于一个正整数列 a1,…,ama_1,\dots,a_m,我们的处理办法就是从小到大枚举区间长度,再枚举这个长度的区间(类似区间 DP),看看这个区间的乘积是否大于加和,如果更大,则直接乘起来合并为一个数,然后继续上述过程。最终就得到了 a1,…,ama_1,\dots,a_m 可以算出的最大结果。

    这个算法的正确性是比较显然的:由于我们从小到大枚举区间长度,因此对于已经枚举过的区间,倘若没有合并,则说明全加是最优的,那么假设当前一个数列 a1,…,ara_1,\dots, a_r 的最优解有 ×\times,若不是全设为 ×\times,则一定形如 $a_1\times\dots\times a_t+a_{t+1}\times\dots\times a_p+\dots$,但 a1,…,ata_1,\dots,a_t 的最优方案是全 ++,因此矛盾,于是只能是全 ×\times,所以我们只需要比较全 ×\times 和全 ++ 即可确定最优解;而依据开始的分析,如果是全 ×\times 则可以直接合并。至此,我们说明了算法的正确性。

    从小到大枚举区间这件事可以通过从小到大枚举右端点 rr,再从大到小枚举左端点 ll 实现,这个过程与处理中缀表达式的栈是类似的,因此可以放一起处理,只不过枚举的 ll 到了最近的 ( 就应当停止。

    原序列的任意一个区间只会被枚举到一次,因此总复杂度 O(n2)O(n^2)。

    需要注意过程中可能得到较大的数,但实际上只要某个数大于了 10910^9,那它与相邻的数(除非是一列 11)必然是相乘优于相加,所以我们只需要记录每个数对 998244353998244353 取模的值,以及它的实际值是否已经大于 10910^9 即可。

    • 1

    信息

    ID
    185
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    3
    已通过
    1
    上传者