会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
改完以后，第 i 个探头的刻度必须是 s+(i−1)⋅d，起点 s 和公差 d 都是非负整数。对不上的探头付维修费，对上的不付。一组的最少费用，就是全部维修费之和，减去某个 (s,d) 上已经对上的探头费用之和的最大值。
每个维修费都是正数，所以选定一组 s,d 之后，凡是刻度已经落在这条等差数列上的探头都留下。做法是按 (d,s) 做哈希累加。
- 下标从 0 计，第 0 个探头就是输入里的 v1。从第 1 个位置起，记该位置下标为 i、当前刻度为 x。它能留下的公差只有 0,1,…,⌊x/i⌋，对应起点 s=x−i⋅d。再大的公差会让起点变成负数。把这个探头的费用加进桶 (d,s)。
- 第 0 个探头只在起点等于 v1 时能留下。公差为 0 的桶直接加上它的费用；公差为正时，只加到已经出现、且起点正好是 v1 的桶。
- 只有一个探头时没有相邻差，费用是 0。
