题解 P7065 【[NWRRC2014]Fragmentation】

JoshAlMan · 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：

• 转移就枚举 (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)。