题解 CF2165D Path Split

· · 题解

题解 CF2165D Path Split

其他题

题意

给定长度为 n 的序列 a，求最少将其划分为多少个子序列，使得划分出的每个子序列中相邻两项之差的绝对值均为 1。

数据范围：多测，\sum n\le 10^6，值域 [1,2n]。

做法

考虑建图，即每个点向编号比它大且差的绝对值为 1 的所有点连边，这时原题变成了最小路径覆盖。DAG 最小路径覆盖一般要转化为二分图最大匹配。

但本题是 10^6 显然直接匈牙利需要大约 31.71 年（不考虑闰年），所以我们要考虑优化。

由于二分图是无向图，所以连边的方式可以改为每个 i 向所有 a_j=a_i+1 的 j 连边，二分图是不变的。

然后发现此时按 a_i 从小往大匹配一定是不劣的。于是这题就变成从小往大枚举 a_i 并尽可能匹配 a_i+1 然后就做到线性（或者 1\log，视实现而定）了。