pku2060专题

PKU2060 Taxi Cab Scheme - 最小路径覆盖

题目描述: 出租车公司接到N(N<500)个订单,每个订单的描述是:t时刻需要从[x,y]坐标出发去[tx,ty]坐标。出租车行驶需要的时间是|x-tx|+|y-ty|。出租车公司希望派出最少的车完成所有的订单。派出一个出租车,它可以去接任何一个订单;若一个出租车在完成了一个订单之后,能在下一个订单的时刻之前赶到出发地点,那么它可以继续接下一个订单。输出最少需要多少出租车。 分析: 将一个订