首页 > 试题广场 >

糖果游戏

[编程题]糖果游戏

热度指数：1478 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小明和小红都很喜欢吃糖果，今天他们一起玩一个糖果游戏。他们将装有不同数量的透明糖果盒子摆放成一个环，现在两人依次选择糖果盒子，小明先拿，且小明第一次挑选可以选择环中任意一个糖果盒子，将环分割成一列有首尾的序列，之后两人每次选择时只能从剩余的糖果盒子序列的行首或者行尾挑选，直到两人将糖果盒子全部拿完，最后糖果多的为胜者。假设两人都希望自己是最后的赢家，且糖果的总数是奇数，现给定一个糖果的环，用一个数组表示环中的各糖果盒子中糖果的数量，数组首尾相连成环，元素个数为N。请输出胜利者比失败者至少多拿多少糖果。

输入描述:

第一行：N
第2至N+1行：每行一个数，代表糖果数

输出描述:

一个数，请输出胜利者比失败者多拿多少糖果

示例1

输入

输出

说明

小明先选择55，此时环从55处断开，变为序列[41, 2, 1]
小红选择行首的41，此时剩余的序列为[2, 1]
小明选择行首的2，此时剩余的序列为[1]
小红选择剩余的1。
此时小明胜利，比小红多15个糖果

算法知识视频讲解

牛客题解官

发表于 2020-06-05 17:37:35

精华题解题解题目难度：中等知识点：动态规划、数组解题思路：首先一看这种根据选择来取最大最小值的题，就应该想到可以使用动态规划进行解题，将整个大问题划分为小问题进行解决。难点主要在考虑怎么将大问题划分为小问题。然后，因为整个可选项是组成"环"的数据形式，所以在选择过程中，使用求余的方式来进行数据采取。整展开全文