题目详情题解（0）讨论（0）提交记录（0）

CF2027A.Rectangle Arrangement

入门

通过率：0%

AC君温馨提醒

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

题目描述

你正在给一个无限大的方格网格上色，初始时所有格子都是白色的。为此，你有 nn 个印章。每个印章是一个宽为 wiw_i、高为 hih_i 的矩形。

你将每个印章恰好使用一次，在网格上以黑色涂色一个与印章大小相同的矩形。你不能旋转印章，并且对于每个格子，印章要么完全覆盖它，要么完全不覆盖它。你可以将印章放在网格上的任意位置，即使被盖住的区域部分或全部已经是黑色也没关系。

在所有印章都使用完后，你能得到的黑色方格连通区域的周长之和的最小值是多少？

输入格式

每个测试点包含多组测试数据。第一行包含测试用例数 tt（1≤t≤5001 \le t \le 500）。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 nn（1≤n≤1001 \le n \le 100）。

接下来的 nn 行中，第 ii 行包含两个整数 wiw_i 和 hih_i（1≤wi,hi≤1001 \le w_i, h_i \le 100）。

输出格式

对于每组测试数据，输出一个整数，表示在所有印章都使用后，黑色连通区域的周长之和的最小值。

输入输出样例

  • 输入#1

    5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2

    输出#1

    20
8
10
400
16

说明/提示

在第一个测试用例中，印章可以如左图所示使用。每个印章用不同颜色高亮显示以便区分。

所有印章都使用后，只有一个黑色区域（如右图所示），其周长为 2020。可以证明，没有其他使用印章的方法能得到更小的总周长。

在第二个测试用例中，第二个和第三个印章可以完全放在第一个印章内部，因此最小周长等于 88。

由 ChatGPT 4.1 翻译

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

首页