会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
旧房落在一条坐标轴上。爆破弹只能投放在某一间旧房里，花费等于覆盖半径。到落点的间距不超过这个半径的旧房会一起被清掉。要求的是把全部旧房清完的最少花费。
- 把坐标 xi 按升序排好。排好以后，一枚弹能清掉的旧房一定是下标连续的一段。
- 枚举落点下标和每一种覆盖半径 r，从落点向左右扩展，得到区间 [L,R]，花费就是 r。P 间旧房、Q 种规格，一共得到 PQ 段。同一种规格会在每个落点上各看一次，所以同一个半径可以投放多次。
- 令 dp[i] 表示坐标最小的 i 间旧房已经清完时的最少花费。dp[0]=0，其余位置先记成无穷大。
- 按 i 从小到大处理。当前最左边还没清的是第 i 间（从 0 编号）时，只使用满足 L≤i≤R 的区间，用花费 r 更新 dp[R+1]。新状态的下标总是大于 i，所以从左到右扫一遍即可。
- 比较时用的是小于等于。落点到自己的距离是 0，最小的半径也盖得住落点那一间，因此一定有解。答案就是 dp[P]。
