loj#P3345. 「APIO2020」粉刷墙壁
「APIO2020」粉刷墙壁
题目描述
注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:
- C++ 11
- C++ 11 (Clang)
- C++ 11 (NOI)
- C++ 17
- C++ 17 (Clang)
距离上一次 Pak Dengklek 在他的家中粉刷墙壁已经过了一段时间,所以他想重新粉刷一次。 他家的墙壁由 段组成, 它们从 到 编号。本题中我们假设存在 种不同的颜色,颜色用从 到 的整数表示(例如, 红色用 表示, 蓝色用 表示,以此类推)。Pak Dengklek 希望用第 种颜色来粉刷第 段的墙壁。
为了粉刷墙壁, Pak Dengklek 雇用了一家有 个承包商的承包商公司,承包商从 到 编号。对 Pak Dengklek 来说不幸的是,承包商只愿意粉刷他们自己喜欢的颜色。具体来说,第 个承包商喜欢 种颜色,并且只想用下列颜色来粉刷墙壁:第 种颜色,第 种颜色,,或第 种颜色。
Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中,Pak Dengklek 将给出两个参数 和 ,其中 。承包商公司将会指派第 个承包商粉刷第 段墙壁,其中 。如果存在一个 使得第 个承包商不喜欢第 种颜色,那么该要求将无效。
Pak Dengklek 需要为每个要求付费,因此他想知道为了使墙壁中每个段都能用自己预期的颜色粉刷,他至少要提出多少个要求,或是确认他的预期无法达到。每一段墙壁可以被粉刷多次,但必须保证每次粉刷的颜色都是 Pak Dengklek 所预期的。
实现细节
你必须引用 paint.h
头文件。
你必须实现 minimumInstructions
函数:
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
该函数将被评测库恰好调用一次。
- :一个整数表示墙壁的段数。
- :一个整数表示承包商的数量。
- :一个整数表示颜色的种数。
- :一个长度为 的整数序列,表示每段墙壁预期的颜色。
- :一个长度为 的整数序列,表示承包商喜欢的颜色数。
- :一个长度为 的每个元素为序列的序列,表示承包商喜欢的具体颜色。
该函数必须返回一个整数,表示 Pak Dengklek 为了让墙壁按预期粉刷所需要提出的最小要求数;若预期无法达到则返回 。
样例评测库
样例评测库将读入以下格式的数据:
N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]
样例评测库将输出函数 minimumInstructions
的返回值。
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
3
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
-1
数据范围与提示
对于 , 令 表示喜欢第 种颜色的承包商数量。
- $0 \le B_{j,0} \lt B_{j,1} \lt \ldots \lt B_{j,A_j-1} \lt K$
子任务 | 附加限制 | 分值 |
---|---|---|
, , | ||
, | ||
, | ||
无附加限制 |