反递增爱好者：题解

思路

偏序与极值

把格子看成偏序集中的元素，定义

题目要求保留下来的点集中最长链长度小于 $k$。由偏序集的对偶 Dilworth 定理，这等价于能用至多 $k-1$ 个反链覆盖全部保留点。

网格中的反链可以扩展成一条只向上或向右走的格点路径。第 $i$ 条互不相交的路径至多包含 $2n-2i+1$ 个格子，因此 $k-1$ 条路径至多覆盖

个格子。这恰好是题目要求保留的格子数。因此合法方案必须由 $k-1$ 条互不相交的最长反链组成：第 $i$ 条路径从 $(n,i)$ 出发，在 $(i,n)$ 结束。

输入为 0 的格子必须保留。于是问题变为：能否让上述路径覆盖所有必须保留的格子。

做法

令 $f_{i,j}$ 表示以必须保留格子 $(i,j)$ 为起点，向右下方严格递增时能取得的最长必须保留点链长；若该格子允许删除，则令 $f_{i,j}=0$。

再令 $mx_{i,j}$ 表示后缀矩形 $[i,n]\times[j,n]$ 中最大的 $f$ 值，则

若 $mx_{1,1}\ge k$，必须保留的格子本身已经含有长度为 $k$ 的链，显然无解。

否则按 $f$ 值分层。对 $i=1,2,\ldots,k-1$，让第 $i$ 条路径覆盖所有满足 $f_{x,y}=k-i$ 的格子。这一层中的任意两个格子都不可比较，因此可以按行从大到小、列从小到大的顺序穿过。

路径从 $(n,i)$ 开始。走向下一个目标格子时，若向上一步不会碰到已经构造的路径，就优先向上；否则向右。最后补到 $(i,n)$。不同路径不会相交，且每条路径长度都达到上界，所以其并集正好保留 $n^2-(n-k+1)^2$ 个格子。

正确性要点

1. 若必须保留点中已有长度为 $k$ 的链，则无论删除哪些允许删除点，这条链都仍存在，所以输出 NO 正确。
2. 同一 $f$ 层是反链；否则较小的点可以接上较大的点，使其 $f$ 值严格更大。
3. 贪心路径优先向上，只在会撞到上一条路径时右移，因此既不会越过本层下一个目标点，也不会与已构造路径相交。
4. 第 $i$ 条路径连接 $(n,i)$ 与 $(i,n)$，含 $2n-2i+1$ 个格子。所有路径互不相交，总保留数达到极值，故删除数恰为要求值。
5. 所有输入 0 都属于某个非零 $f$ 层并被对应路径覆盖，所以只会删除允许删除的格子。

复杂度

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；多组数据的总复杂度为 $O(\sum n^2)$。

子任务算法

子任务 1：枚举删除集合

当 $n\le4$ 时，枚举所有允许删除格子的子集，筛选大小恰为 $(n-k+1)^2$ 的集合，再用二维前缀最大值检查剩余点的最长链。该算法是独立的完备搜索。

子任务 2：$k=n$

在 $n\times n$ 网格中，长度为 $n$ 的严格递增链只能是主对角线。只需在主对角线上找一个允许删除的格子并删除；若找不到则无解。

子任务 3：最小费用最大流

把每个格子拆成入点和出点，容量为 $1$；必须保留格子的点边费用为 $-1$，其他点边费用为 $0$。加入向上、向右的转移边，从 $(n,i)$ 向 $(i,n)$ 发送 $k-1$ 单位流。若最小费用等于必须保留格子数的相反数，则所有必须保留格子都被互不相交的路径覆盖。该算法复杂度约为 $O(kn^2E)$，足以通过 $n\le60$。

输出验证

本题使用 Testlib 特判：检查可行性结论、删除数、删除权限，并用二维前缀最大值重新计算剩余网格的最长严格递增链。任何合法构造均可通过。