第4题

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

第 2/6 步：计算策略救下的房屋

上一步下一步

2[(n-1)+(n-2)+\cdots+(n-c)]+(n-2c)(n-c)=n^2+c^2-nc-c

详细分析

在距第 c 列分别为 0,1,...,c−1 的对称列对中,策略分别救下 n−1,n−2,...,n−c 座房屋。其余 n−2c 列每列救下 n−c 座。总数为 n 的平方+c 的平方−nc−c。