一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 299|回复: 3
收起左侧

[算法题] 问下题解法

[复制链接] |试试Instant~ |关注本帖
mlfma 发表于 2015-9-26 02:52:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
网上看来下面这个题, 一点思路没有,请各位大拿给点提示:-)

桌子上有3n个object围成一个圈, 每个object都有一个value, 你和你的两个好朋友每次各从桌子上拿一个,你先选,之后你的朋友再选,而且你的朋友只能拿你拿的那个object的左右相邻的两个。问如何才能让你自己拿的objects的value的总和最大?(注意不是总和比朋友大,而是在自己所有不同拿法中总和的值最大)
stellari 发表于 2015-9-26 12:35:46 | 显示全部楼层
确认一下,
1. object数目是3n,也就是3的倍数?
2. “最大”指的是在朋友使用“使朋友自己收益最小化”还是“使自己收益最大化”的策略下你得到的值呢?看你的说法,好像是前者?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-26 12:45:32 | 显示全部楼层
如果朋友是为了配合你拿到所有拿法的最大可能的话,这题就比较简单:比如有2n个数字,那么先找出其中较小的n个值(记为O)和较大的n个值(记为X)。那么,这个圈可能看起来就是:
OOOXXOOOOXXOXXXX->back to 0
这个样子
那么从圈中任意一点开始,任意方向(比如顺时针)旋转。当找到了第一个“前面是O的”X时,那么“你”就拿这个X,然后朋友拿其前面的O。然后重复这个过程。到最后“你”拿的一定都是X,也就是最大的n个,朋友拿的一定是最小的n个。因此“你”的收益一定是最大化的。用O(n)额外内存的话,这算法可以用O(n)时间实现。
回复 支持 反对

使用道具 举报

 楼主| mlfma 发表于 2015-9-27 03:37:06 | 显示全部楼层
stellari 大贤,我觉得是使自己收益最大化。我也是从网上看来的题。我的理解是我pick了一个后,两个朋友只能pick左右两边的value,然后continue

能不能用您老形容的Grundy方法解啊?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 13:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表