自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 22:26:19，当前版本为作者最后更新于2021-01-21 16:28:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑降序的必须断开，离散化后不连续的必须断开，序列就变成大概是若干递增串（称之为块，给这样的每个块编个号qwq）的形式，然后可以连起来的段要满足的性质（充要）：

• 如果三个以上不同数值连起来，被包含在中间的数必须恰好所有同数值都在这个段里，否则就拼不进来了。
• 离散化后，连接 $(x, x+1)$ 这样的东西最多连一次。

如果假设最开始全断的化，要最大化连的次数。

这个东西似乎很难做，每段并不是独立的，看样子需要按数值顺序做安排。

想到（我就想不到呜呜呜）如果 $\le x$ 要如何连都安排好了，那么后续再连，前面对后面决策的可行性有影响的只有 $(x - 1, x)$ 有没有连，连的哪个块：

• 如果 $(x, x+1)$ 不准备连那么不影响
• 若 $(x, x +1)$ 连的块不是 $(x - 1,x )$ 的块，那么显然咋搞都行
• 如果是相同的块，那么就要检查是否 $x$ 全部出现在这个块作为可行的要求。

因此我们可以设一个 DP：

• $f_{i, j}$ 表示连接到数值 $i$，$(i - 1, i)$ 连的块编号是 $j$（没连搞成 $0$），最大化连的次数。

• 转移就枚举 $(i - 2, i - 1)$ 连的块是啥

  • $f_{i,0}=\max(f_{i-1,j})$

  • $f_{i, j} = \max_{k\not= j}(f_{i - 1, k} + 1)$

  • 同一块内的转移要满足 $i - 1$ 全部出现在这个块里，式子也是同上。

别看是二维 DP，但实际的状态数应该是 $O(n)$ 的，因为每一个状态都一一对应着一个块内连续对。

然后考虑转移，暴力转移是 $O(n^2)$ 的。优化也挺显然，前后缀 $\max$ 再加自身转移特判，每次转移做到 $O(1)$。（具体实现来回扫一遍双指针）

总复杂度 $O(n)$。