题解：P8388 [COI2021] Cigle

· · 题解

提供一个 O(n^2\log_2{n}) 做法（其实是因为本蒟蒻赛时 n^2 做法死活调不对）。

由于题目说是按顺序摆的，所以每一行都是一个区间，可以想到分段 dp。

用 dp_{l,r} 表示前 r 个数最后选了区间 [l,r] 的最大美丽度，枚举上个区间 [k,l-1]，dp_{l,r}= \max_{k=1}^{l-1} dp_{k,l-1}+s 。

这里的 s 代表 [k,l-1] 与 [l,r] 产生的美丽度，即 [k,l-1] 中的后缀和与 [l,r] 中的前缀和相同的个数，注意前缀或后缀不能是其本身（排除两砖共点）。

维护前缀和，然后暴力计算 s 即可得到 O(n^5) 做法。

s_{l-1}-s_{p}=s_q-s_{l-1} s_q+s_{p}=2s_{l-1}

枚举 p，在从小到大枚举 r 时顺便用桶记录 [l,r] 里有多少个 q 满足 2s_{l-1}-s_{q}=s_{p} ，每次加入 2s_{l-1}-s_{r}，即可得到 O(n^4) 做法 虽然还是 20 pts。

注意到 p \in [k,l-2]，所以我们倒序枚举 k，对于每个 k 加入 k 的贡献，得到 O(n^3) 做法。

考虑 2s_{l-1}-s_{r} 产生的贡献，用双指针求出 s_p=2s_{l-1}-s_{r} 的 p，我们发现如果要让 p \in [k,l-2]，那么 k \in [1,p]，相当于对 [1,p] 的 dp_{k,l-1} 加一，最后 dp_{l,r}= \max{dp_{k,l-1}}。

区间加，全局 max，用线断树即可。

满分做法。

希望洛谷早日恢复讨论区。