题解：AT_arc117_e [ARC117E] Zero-Sum Ranges 2

· · 题解

[ARC117E] Zero-Sum Ranges 2

以下的图皆引用自 atcoder 官方题解。

有点牛的 dp 题。

先考虑没有前缀和小于 0 的情况怎么做。类似于 [JOI Open 2016] 摩天大楼 / Skyscraper，观察最终的序列的前缀和长相可以发现是一个每次上升一个或下降一个的样子，如图：

注意到值相同的位置都在同一层中，考虑分层 dp，每次将一个数插到一个位置。那么当前的状态会形成若干个段，且每一个段的两端一定是当前枚举到的这个元素，因此我们不需要知道段的具体信息，只需要知道其数量。

继续观察性质。注意到因为相邻两个位置的差值只能是 1 或 -1，所以假设上一次插入的是那些值为 x 的位置，那么对于一个段，其向左右延申出来的数一定是 x-1，因此我们可以考虑从高位到低位进行 dp。

设 f_{i,j,k} 表示插入了 i 个数，这些数中选择两个值相同的位置的选法为 j，一共分成了 k 段。转移枚举当前这个值的数量，设为 l，有转移：

f_{i,j,k}\times \binom{l-1}{k}\longrightarrow f_{i+l,j+\frac{l\times(l-1)}{2},l-k}

其中 \binom{l-1}{k} 是将这 l 个数分成 k+1 段，直接插板。添加这些数后段数为 l-k 的原因是在没有段数的情况下是 l-1 个空位，每出现一个原来有的段就会将两个位置隔开导致空位减少，所以一共有 l-1-k 个空位，也就是 l-k 段。

然后考虑存在前缀和为负数的情况。不难发现其实正负是倒着的相同的问题，枚举大于等于 0 的数量和段数即可。

时间复杂度 \operatorname{O}(n^5)，可以通过。