kblack edited 6 年,10 月前
This is a past version of blog 锅
小学物理期末考试
显然,在这个问题中对于重心我们只需考察它的横坐标。考虑第 $i$ 块砖块及其至上所有的砖块,其重心一定落在第 $i$ 和第 $i-1$ 块砖块的范围内,定义 $f(i)$ 为第 $i$ 块及之上所有的砖块,最右侧的砖块能超出的重心位置的距离。显然我们可以将所有砖块的重心控制在桌缘上,从而 $f(1)$ 即是我们要求的答案。
考虑第 $i$ 块砖块的情况,其重心由当前砖块的重心(1/2处)和其上所有砖块的重心(对于第 $i$ 块砖,这是一个定值)加权中点,这时有两种策略:当前砖即是最右侧的砖块,此时我们不用考虑其上砖块能超出其重心的距离;当前砖不是最右侧的砖,我们希望让上面的砖的重心尽可能的超出。两种情况在下图中给出。
$f(i) = max(f(i+1)+1-delta, 1+delta)$
$delta = \frac{m_i}{\sum_{j=i}^n{m_j}}$
从 $f(n) = 1$ 开始递推,我们就可以得到所有的答案 $f(1)$。