AT_joig2021_f.デジタルアート (Digital Art)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 高中的学生葵喜欢制作数字艺术作品，今天她又创作了一幅新图片。

这幅图片的尺寸是 $ H $ 行 $ W $ 列，可以用一个 $ H \times W $ 的网格来表示。行号从上到下为 $ i $（$ 1 \leq i \leq H $），列号从左到右为 $ j $（$ 1 \leq j \leq W $）。每个像素都有一种颜色，颜色编号为从 1 到 256 之间的一个整数，像素 $ (i, j) $ 的颜色编号为 $ A_{i, j} $。

葵将这幅作品展示给她的同学凛，但凛认为图片中使用的颜色种类过多，因此不太喜欢。为了让凛满意，葵决定隐藏图片中的某些区域，以尽可能减少可见的颜色种类。

葵可以选择最多 $ S $ 个像素进行隐藏。
需要注意的是，隐藏的像素必须构成一个矩形区域。

给定图片的数据和隐藏像素的数量上限 $ S $，编写一个程序，计算在隐藏某个区域后，最少能看到多少种颜色。

输入格式

输入通过标准输入提供，格式如下：

$ H\ W\ S\ A_{1,1}\ A_{1,2}\ \cdots\ A_{1,W}\ A_{2,1}\ A_{2,2}\ \cdots\ A_{2,W}\ \ldots\ A_{H,1}\ A_{H,2}\ \cdots\ A_{H,W} $

输出格式

输出在一个区域被隐藏后，可能可见的最少颜色种类数。如果可以隐藏所有像素，从而没有可见像素，则输出 0。

输入输出样例

输入#1
```
1 10 7
5 1 2 5 2 2 5 6 6 5
```
输出#1
```
2
```

输入#2

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

输出#2

输入#3

5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

输出#3

输入#4

9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

输出#4

输入#5

8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

输出#5

说明/提示

约束条件

$ 1 \leq H \leq 1,000 $。
$ 1 \leq W \leq 1,000 $。
$ 1 \leq S \leq HW $。
$ 1 \leq A_{i, j} \leq 256 $ （$ 1 \leq i \leq H $，$ 1 \leq j \leq W $）。
所有输入值均为整数。

子任务

（8 分）$ H = 1 $，$ W \leq 10 $。
（10 分）$ H \leq 10 $，$ W \leq 10 $。
（5 分）$ S = 1 $。
（6 分）所有颜色编号 $ A_{i, j} \leq 2 $。
（5 分）所有颜色编号 $ A_{i, j} \leq 4 $。
（13 分）所有颜色编号 $ A_{i, j} \leq 15 $。
（13 分）所有颜色编号 $ A_{i, j} \leq 30 $。
（15 分）所有颜色编号 $ A_{i, j} \leq 70 $。
（25 分）无其他限制。

评分标准

所有提交将在评测系统中评分。

只有当程序为每个子任务的所有测试数据返回正确结果时，该子任务才被认为是正确的。

提交程序的得分是根据其成功解答的所有子任务的分数总和计算的。

最终得分是所有提交中的最高得分。

你可以在“提交结果”标签页中查看当前得分。

样例解释 1

例如，隐藏第 2 列到第 8 列的像素后，仅能看到颜色编号为 5 和 6 的像素，颜色种类数为 2。这时，隐藏了 7 个像素，满足条件。葵无法使可见颜色种类少于 2，因此输出 2。此输入满足子任务 1、2、6、7、8 和 9 的限制。

样例解释 2

例如，隐藏以像素 $ (2, 1) $ 为左上角和 $ (7, 7) $ 为右下角的矩形区域后，仅能看到颜色编号 1、3、4 和 5，颜色种类数为 4。这时，隐藏了 42 个像素，满足条件。如下图所示：此输入满足子任务 2、6、7、8 和 9 的限制。

样例解释 3

在最多只能隐藏 $ S = 1 $ 个像素的情况下，葵无法减少可见颜色种类，仍能看到 1 到 9 的 9 种颜色。因此输出 9。此输入满足子任务 2、3、6、7、8 和 9 的限制。

样例解释 4

可以隐藏所有 54 个像素，使没有可见像素，因此输出 0。此输入满足子任务 2、6、7、8 和 9 的限制。

样例解释 5

例如，隐藏以像素 $ (3, 1) $ 为左上角和 $ (10, 7) $ 为右下角的矩形区域后，仅能看到颜色编号为 1 和 3，颜色种类数为 2。这时，隐藏了 56 个像素，满足条件。如下图所示：此输入满足子任务 2、5、6、7、8 和 9 的限制。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页