洛谷P2285 【[HNOI2004]打鼹鼠】

每次打鼹鼠的机器人总是从某一次打鼹鼠的地方走过来的

对鼹鼠出现时间从小到大排序

f[i]表示到第i个鼹鼠（打第i个）最多能打多少个鼹鼠

$f\left[i\right]=max\left(f\right[j]+1)$f[i]=max(f[j]+1) 要求 $\mid xj-xi\mid +\mid yj-yi\mid \&lt;=time\left[i\right]-time\left[j\right]$∣xj−xi∣+∣yj−yi∣<=time[i]−time[j]

时间复杂度 $O\left(m^2\right)$O(m2)