CF1738G Anti-Increasing Addicts

Alex_Wei · 2022-10-16 12:12:20 · 题解

果然还是 Anton 出的题最智慧。

初步感知问题：

• 当没有限制一些位置必须保留时，直接删去 (n - k + 1) \times (n - k + 1) 的正方形即可满足条件。

• 题目要求不能出现保留位置不出现长度为 k 的链，根据 dilworth 定理，必须用不超过 k - 1 个反链覆盖所有保留位置。

设 f_{x, y} 表示从 (x, y) 开始的只经过保留位置的最长链长度。显然若存在 f_{x, y} = k 则无解，因为我们被强制保留长度为 k 的链。否则我们尝试用 k - 1 条反链在最大化覆盖位置的同时，覆盖到所有强制保留的位置。

根据 f_{x, y} 的值将位置分层，值相同的位置必然形成一条反链，否则 p\to q 形成链，f_p 可以更大。

为了让最大化覆盖位置，不妨设第 i 条反链从 (n, i) 开始，每次向上或向右走，经过所有未被覆盖的 f 值为 k - i 的位置并将经过的点全部覆盖，最终走到 (i, n)。若反链互不相交，则覆盖位置之和为 \sum_{i = 1} ^ {k - 1} 2(n - i) + 1，达到最大值。

为此，我们规定反链 能向上走就向上走。也就是说，当且仅当上方已经被覆盖或再往上走就无法覆盖某个 f 值为 k - i 的位置时，我们才会向右走。为此，设 lim_{v, y} 表示第 y 列及其右侧 f 值为 v 的位置的行数最大值，若当前 x = f_{k - i, y + 1} 则无法继续往上走，否则无法覆盖 y + 1 及其右侧 f 值为 v 的行数最大的位置。

如上图。

只需证明第 i 条反链必然经过 (n - k + i, i) 和 (i, n - k + i) 即可证明合法方案一定存在，而这是容易的。对于第 i 条反链，在第 i + 1 列及其右侧不会出现行数大于 n - k + i 的 f 值为 k - i 的位置 (x, y)，其中 x > n - k + i，因为否则其对应链末端的行数 x' \geq x + (k - i) > n，不合法。因此，根据 尽量向上走 原则，从 (n, i) 出发一定可以走到 (n - k + i)。同理可证最终必然经过 (i, n - k + i)。