CF1720E Misha and Paintings 做题记录

给你一个 $n\times n$ 的矩阵 $a$ 和一个正整数 $k$，你可以对 $a$ 进行任意次操作（可以不操作），操作的具体步骤如下：

• 选择矩阵 $a$ 的一个正方形子矩阵；
• 选择一个正整数数 $x$，其中 $1\leq x\leq n^2$；
• 将子矩阵内的所有元素修改为 $x$。

你需要求出使矩阵 $a$ 恰好包含 $k$ 个不同元素所需的最小操作次数。

$1\le n\le 500,1\le k\le n^2$。

设操作前有 $cnt$ 个不同元素，那么若 $k\ge cnt$ 则答案一定是 $k-cnt$，因为一次操作最多增加一个不同元素。

考虑 $k<cnt$ 的情况，可以证明最多只需要两次操作：

• 考虑选择一个以 $(1,1)$ 为左上角的最大的正方形使得它全部替换成 $a_{1,1}$ 后 $a$ 中不同元素个数 $\ge k$ 且最小；

• 接下来这样选择第二个正方形：

  

  因为这个正方形可以选择与第一个的 $x$ 相同或不同，所以总有一个满足操作完之后 $a$ 中恰好有 $k$ 个不同元素；

那么只用判断 $1$ 次和 $0$ 次是否可以即可，做法很显然。