MathLabs

第4题

在一个 n×n 的小镇中,房屋编号为 (i,j),左上角为 (1,1)。时刻 0 房屋 (1,c) 起火,其中 c≤n/2。每个单位时间内,消防员保护一座尚未着火的房屋,随后火焰从时间段开始时着火的每座房屋蔓延到所有未保护的相邻房屋;已保护房屋始终受保护。最多能救下多少座房屋? 相邻指恰有一个坐标相差 1。
第 5/6 步：计算上界
上一步下一步
∑t=1n−1s(t)≤∑t=1n−1t,∣{ℓ>n−1}∣=n2−n(n−1)2−c(n−c+1)\sum_{t=1}^{n-1}s(t)\le\sum_{t=1}^{n-1}t,\quad |\{\ell>n-1\}|=n^2-\frac{n(n-1)}2-c(n-c+1)
详细分析

因此在不超过 n−1 的层上至多救下 1 到 n−1 的和。直接计算这些层的网格点数为 n(n−1)/2+c(n−c+1);其余各层共有 n 的平方减去该数座房屋。