P10509 停车场题解

给出一个

n\times n

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

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

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

假如这个停车场是一条直道，显然最多能有

6

个，就像下面这个（以下用

1

代表车位，

0

代表空地）：

CPP

111111111111111111
000000000000000000
111111111111111111

因此我们得到答案上界：

\dfrac{2n^2}{3}

。

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

因此我们需要加入弯道。

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

CPP

011
100
101

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

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

CPP

因此最终的弯道数量为

\dfrac{2n}{3}

，答案为

\dfrac{2n^2-2n}{3}

。

文章操作