P10509 停车场 题解

ARIS0_0 · 2024-12-13 12:12:04 · 题解

1. 题目解释

给出一个 n\times n 的矩阵，要求在这个矩阵中放置车位使得每个车位都能通向出口，问车位最多的数量。

2. 思路

暴搜显然是不行的，因此我们考虑贪心。

首先我们考虑，一个空地附近最多能有几个车位。

假如这个停车场是一条直道，显然最多能有 6 个，就像下面这个（以下用 1 代表车位，0 代表空地）：

111111111111111111
000000000000000000
111111111111111111

因此我们得到答案上界：\dfrac{2n^2}{3}。

显然这不是答案，因为如果全部直排，上方的所有车位都到不了出口。

因此我们需要加入弯道。

考虑一个弯道处的车位数量：

011
100
101

在每一个弯道处都会减少一个车位，因此我们考虑统计弯道数量。

如果我们采用回形道路，容易发现每三行就会出现两个弯道，比如：

011111110
100000001
101111101
101101101
101101101
101101101
101101101
101100001
001111111

因此最终的弯道数量为 \dfrac{2n}{3}，答案为 \dfrac{2n^2-2n}{3}。