Codeforces Round #752 Extreme Extension 题解 (Java/C++)

题解

显然，我们不需要考虑操作顺寻。因此我们直接考虑对某一个数会如何执行若干次操作。
同样是显然的，经过若干次操作后，我们希望拆分出的数字尽可能平均。
以4为例，如果我们要将4拆成2个数，一定是拆成2和2，而非1和3。因为如果拆成1和3，一方面会迫使前面的数字拆分成更小的数字，二方面会使最大值增大。

于是我们发现，对于任意的$a_i$，经过若干次拆分后的值只有$\sqrt a_i$种可能。
以$a_i=100$为例，假设$a_{i+1}=40$。我们不会将$a_i$拆分成$[20, 40, 40]$，而是拆分成$[33, 33, 34]$。
再以$a_i=100$，$a_{i+1}=3$为例。显然，我们会将其拆分为32个3和2个2，总共34个数。而不难发现，同样的以3为最大值，2为最小值，还有拆分成35个数的方法，但是其实我们只关注最小的拆分。

于是对于$a_i$，我们维护拆分后的最大值与拆分所需的操作数之间的映射。我们分两块来维护：

1. 令m表示操作次数，对于$m \leq \sqrt a_i$的，$map[\left\lceil \frac{a_i}{m} \right\rceil]=m-1$。
2. 对于$m>\sqrt a_i$的，令k表示若干次操作后剩下的最大值，显然有$m=\left\lceil \frac{a_i}{k} \right\rceil$，且$k<\sqrt a_i$。于是有$map[k]=\left\lceil \frac{a_i}{k} \right\rceil$

因此对于每一个$a_i$都可以在$O(\sqrt a_i)$的时间内完成映射。
我们用$count[a_i][j]$来表示将$a_i$拆分成最大值为j，需要多少步。这里需要注意的是，j并不连续。

有了这个映射，我们就能给出如下的dp定义：dp[i][j]表示以$a_i$结尾的子串，拆分后最后一位为j时（也就是最大值为j时），extreme values的总和。同样的，需要注意，j并不连续。
于是有：$dp[i][j]=count[a_i][j] \cdot i \cdot dp[i-1][k]$，其中k是dp[i-1]中，存在的，且是小于等于j的，最大可能的值。同时，因为以$a_i$结尾的子串共有i个，因此count[a_i][j]需要乘以i。

而最终的答案就是$\sum dp[i][a_i]$。

最后，同时考虑内存开销和时间开销，我们要做以下优化：

1. 因为dp[i]只与dp[i-1]有关，因此显然是可以应用状态压缩。
2. 虽然$count[a_i][j]$和$dp[i][j]$中的j并不连续，但我们发现，在计算count和dp过程中，j不论是在查询时还是写入时，都是有序的。因此，我们可以使用数组和下标而非map来完成记录和查询。使用map的复杂度为：$O(n\cdot \sqrt a \cdot log(\sqrt a))$，而不使用map的复杂度是：$O(n\cdot \sqrt a)$。

代码

Java

C++