我要招人

去企业版

首页 > 试题广场 >

给50个硬币,面值可以不同,排成一排,两个人轮流取,只能从两

[问答题]

给50个硬币,面值可以不同,排成一排,两个人轮流取,只能从两端取,先取的人如何保证取到的币值大于等于另一个人

甚是无聊

首先计算奇数位金额大还是偶数大，如果奇数大，就先拿第一位的硬币，然后跟着另一个人拿硬币，保证你拿的都是奇数位，偶数大同理，若一样大，就可看成奇数大或偶数；

发表于 2016-02-21 13:31:27 回复(1)

haowg

奇数大拿奇数，偶数大拿偶数。然后就是他拿哪边我拿哪边保证奇偶不变

发表于 2015-07-08 18:37:38 回复(0)

SelForcmiles

明显动规dp的题啊，f[i][j]=max(num[i] + sum[i+1][j] - f[i+1][j] , num[j] + sum[i][j-1] - f[i][j-1])

f[i][j]表示从i到j取的最大和

sum[i][j]表示从i到j的和

每次只需判断拿左边大还是右边大就好了

发表于 2017-03-23 15:48:28 回复(3)

万QQ

既然是两个人轮流取，则率先想到奇偶判断，将奇数位的和和偶数位的和做比较，若是奇数位大则选取奇数序号，反之则选偶数序号。

发表于 2015-06-19 10:58:35 回复(0)

快乐记忆

按面值排序，两个人分别从两端取，就可以保障一个总额大于等于另一个

发表于 2019-08-10 17:46:51 回复(0)

wanye_z

一共50个硬币。首先看看奇数和以及偶数和的大小，如果偶数和大，那么我就每次取偶数，并且因为一共是50个，我是可以保证的；当然，如果奇数大，那么每次就取奇数，同样，这个也是可以保证的。

但是如果总数不是50而是51后者49，我们就无法保证了。那么这道题该如何解？

发表于 2017-09-11 10:51:36 回复(0)

冰菓

动态规划的算法怎么设计啊

发表于 2015-08-11 01:21:43 回复(0)

小小娃爱吃甜食

先给所有硬币编号，计算奇数位的和和偶数位的和，比较，奇数位和大则取基数，否则反之。如果相同，就要采用动态规划了

编辑于 2015-07-10 11:13:53 回复(0)

我呀哈哈哈

我理解的是每个人每次从开始或最后取硬币，每次取一枚：
方法：看前两个和最后两个，找其中的最大值，如果最大值在外侧（即在开头或结尾），那么就取走最大的；如果最大面值的不在最外侧，就取走非最大面值硬币所在侧的最外侧硬币（比如，最大面值在开头那一侧，就取结尾那一侧的最外面的硬币）

发表于 2015-06-02 22:10:31 回复(0)

陈木木

看奇数位的数的和以及偶数位的数的和哪个大，若奇数位的***第一个，否则选最后面的（这里假设奇数位和偶数位的和不同）若出现相同，可以采用动态规划的思路来做

发表于 2015-05-05 14:37:34 回复(1)

提交观点

问题信息

智力题

上传者：陈木木

难度：

10条回答 168收藏 10956浏览

给50个硬币,面值可以不同,排成一排,两个人轮流取,只能从两

问题信息

热门推荐

相关试题