第4题

在一个 n×n 的小镇中,房屋编号为 (i,j),左上角为 (1,1)。时刻 0 房屋 (1,c) 起火,其中 c≤n/2。每个单位时间内,消防员保护一座尚未着火的房屋,随后火焰从时间段开始时着火的每座房屋蔓延到所有未保护的相邻房屋;已保护房屋始终受保护。最多能救下多少座房屋? 相邻指恰有一个坐标相差 1。

第 6/6 步：使构造达到上界

上一步下一步

\left[n^2-\frac{n(n-1)}2-c(n-c+1)\right]+\frac{n(n-1)}2=n^2+c^2-nc-c

详细分析

对角线策略救下所有高于 n−1 层的房屋,而归纳法给出低层可能的最大数。两部分相加化简为 n 的平方+c 的平方−nc−c,故这就是最大值。