谷歌 上门

楼主能说一下第五题dfs+cache的具体做法吗

FTD2014 发表于 2018-6-21 03:00
想问一下关于第五题，每次拿的时候，是只知道前三张是多少值，还是后面所有牌的值和顺序都是知道的

都是明牌

nibuxing 发表于 2018-6-21 10:25
楼主能说一下第五题dfs+cache的具体做法吗

因为你dfs下去求解，那么会有很多状态是重复的。所以用一个map存一下算过的状态。比如说在i这个位置开始拿牌，a[i]表示在i这个位置第一个人能拿到的最多分数，b[i]表示另一个人能拿到的最多分数。那么a[i] 就应该在 sum[ i - i + k] + b[ i + k], k 小于3 ，之间挑一个值，相应的能够算出b[i]来，不知道我说清楚了没有。

lz第三题是要对每个rectangle都要储存之前split的各种小rectangle吧？怎么处理这块的？

楼主能具体说说用dfs怎么去求解吗？如果用dfs的话，那么另外一个玩家的情况怎么处理呢？
谢谢！

第三题好像skyline problem

第五题感觉是博弈型动态规划