登录
  • #刷题
  • #树/链表/图

一道似乎用DP也不能解决的题: diamond mine

siriuxy
4355
14
最近做到一道很难的题目,用DP并不能解决。请先读题:

http://imgur.com/a/58bK3

提出DP做法的同学,我问你一个问题,如果从起点到终点的时候是取的能采集最多diamond的情况,那么这是否会破坏从钟点回到起点的路径,导致回程的路上采集不到很多diamond?因为每一个采集路径都会对地图上剩余diamond 的分布造成影响,那么采用这种greedy的做法如何才能证明 Max(start->end, new map)+Max(end->start, map after max(s->e)) = Max(start->end->start, new map)?
14条回复
热度排序

发表回复