hdu4341专题

hdu4341 Gold miner 分组背包dp

题意:和黄金矿工差不多。。人在(0,0)。有n种金,游戏时间为T。告诉你每种金的位置(x,y),获得该金需要的时间的t,以及它的 价值。且若人和多块金子共线时,只能先取最近的金子。问在游戏时间内可获得最大价值。 思路:对于共线的金,我们将其分为一组,并按照距(0,0)的距离排序,那么选该点的价值为前面所有的价值,花费的时间也是前 面所有花费的时间。对于每组我们相当于只选一个,之后背包跑一下