题目链接
## 题意
黄金矿工游戏,应该都玩过把,给你每个矿石的坐标,以及获取他的所需的时间以及你可以得到的价值,问你可以在规定时间内可以获得的最大价值。有个问题是,如果这两个矿石位于同一条直线上,必须是先把较近的矿石获取完毕才能获取后面的矿石。
## 思路
我们可以把位于同一条直线上的矿石合并,让较远的矿石的时间所需再加上等于他前面的矿石的时间之和,价值也是如此。那么这样的话,我们可以把位于同一条直线上的矿石看成一个组,我们每次只能在每个组中选取一种情况。这样就转换成了分组背包。
1 |
|
云腾致雨,露结为霜
1 | #include <iostream> |