CF436D Pudding Monsters

你玩过 Pudding Monsters 吗？在本题中，我们使用了该游戏的一个简化版一维模型。 想象有一条无限长的格子带，其格子依次被编号为整数。带上的某些格子上有怪兽，其他的格子则是空的。所有的怪兽都是布丁做的，因此如果有两个怪兽在相邻的格子上，它们会粘在一起。同理，如果有多个怪兽连续地站在若干格子上，它们会全部粘成一个怪兽块。我们称这些粘在一起的怪兽为一个怪兽块。没有与其它怪兽相粘的落单怪兽，也被认为是一个怪兽块。 在一次操作中，玩家可以任选一个怪兽块，用手将其向左或向右扔去。被选中的怪兽们会一直滑动，直到碰到其他怪兽（或怪兽块）为止。 例如，若有一条带子上，第 $1$、$4$、$5$ 号格子上各有一个怪兽，那么一共只有四种可能的操作：将 $1$ 号格子的怪兽扔向负无穷，将 $4$、$5$ 号格子的怪兽块扔向正无穷，将 $1$ 号怪兽向右扔（它会停在 $3$ 号格子），将 $4$、$5$ 号怪兽块向左扔（它们会停在 $2$ 和 $3$ 号格子）。 带子上的某些格子上标有星号，这些是特殊格子。游戏的目标是让尽可能多的特殊格子上有怪兽。 现在给定了带子上特殊格子的位置和初始所有怪兽的位置，求在最优策略下，最多能有多少个特殊格子上被怪兽占据。

第一行输入两个整数 $n$ 和 $m$，$1 \leq n \leq 10^{5}$，$1 \leq m \leq 2000$，分别表示带子上的怪兽数和特殊格子数。 第二行输入 $n$ 个互不相同的正整数，表示怪兽所在的格子的编号；第三行输入 $m$ 个互不相同的正整数，表示特殊格子的编号。保证所有格子编号均为正整数且不超过 $2 \cdot 10^{5}$。

输出一个整数，即在最优策略下，最多有多少个特殊格子上能有怪兽。

由 ChatGPT 5 翻译