首页 > 试题广场 >

糖果游戏

[编程题]糖果游戏

热度指数：1445 时间限制：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个糖果

算法知识视频讲解

Python

深海水蜇

dic={}
def res(ary):
    if not ary:
        return 0
    if not ary in dic:
        dic[ary]=min(-res(ary[1:])-ary[0],-res(ary[:-1])-ary[-1])#对于对手来说，对手得分是负的自己得分
    return dic[ary]
a=int(input())
aa=[int(input()) for _ in range(a)]
print (abs(max([-res(tuple(aa[i:]+aa[:i])) for i in range(a)])))

发表于 2019-06-27 15:06:51 回复(0)