自动搬运

查看原文

来自洛谷，原作者为

	rhn7 洛谷用户数：1789309

搬运于2025-08-24 22:38:39，当前版本为作者最后更新于2025-01-16 17:17:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一个 $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，用线断树即可。

满分做法。

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