风衣. 2023-03-17 12:06 采纳率: 100%
浏览 39
已结题

c++数据结构题求解!

数据结构学不懂,求解
题目描述
亚历克斯和辛迪,两个学生最近花了一些时间来寻宝。除了废金属外,他们还发现了一些装满旧硬币的盒子。盒子的值不同,现在排列成一行。辛迪提出了一个把宝藏分成两部分的想法。她认为公平的方式是她和亚历克斯轮流,每个人从线的左边或右边选择一个盒子。辛迪是个非常大方的人,让亚历克斯先选。

亚历克斯想看看这个主意是否真的对他有好处。他让你写一个程序来计算他将得到的总价值和辛迪如果他先选了一个盒子会得到多少。你可以确信他们都是非常聪明的,并且总是以这样的方式选择下一个盒子,从而为他们带来最佳的整体个人解决方案。这意味着他们可能不会总是选择当前可用的两个值最高的框,以确保他们以后得到一个值更高的框。

输入输出格式
输入格式
第一行输入整数,表示一些装满旧硬币的盒子,每个整数用一个空格隔开;
输出格式
一行输出整数,表示他将获得的总价值与辛迪首先选择一个盒子将获得的总价值进行比较的结果。

输入输出样例1
输入
7 2
输出
5
解释(可选)
亚历克斯会选7,辛迪会选2,所以结果是7‐2=5。

输入输出样例2
输入
2 7 3
输出
-2
解释(可选)
亚历克斯选择 2 还是 3 并不重要,辛迪会选择7,亚历克斯将得到剩下的盒子,(2+3)‐7=‐2。

说明提示
该函数应该返回alex value–cindy value

  • 写回答

3条回答 默认 最新

  • lshen01 2023-03-17 12:11
    关注

    参考GPT和自己的思路:

    这道题目需要用到动态规划的思想,具体的做法是,维护一个二维的数组 $f[i][j]$,表示当剩下的盒子为 $i$ 到 $j$ 时,先手能够获得盒子总价值减去后手能够获得盒子总价值的最大值。初始状态为 $f[i][i]=a[i]$,表示只剩下一个盒子时,先手获得价值为该盒子的价值,后手获得价值为 $0$。

    状态转移方程如下:

    $$f[i][j]=\max{a[i]-f[i+1][j],a[j]-f[i][j-1]}$$

    其中,$a[i]$ 表示第 $i$ 个盒子的价值。上式表示,当先手选了第 $i$ 个盒子时,他能获得的价值为 $a[i]$ 减去后手在剩余盒子中的最大收益,即 $f[i+1][j]$;同理,当先手选了第 $j$ 个盒子时,他能获得的价值为 $a[j]$ 减去后手在剩余盒子中的最大收益,即 $f[i][j-1]$。

    最终的答案即为 $f[1][n]$,其中 $n$ 表示盒子的总数。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 4月20日
  • 已采纳回答 4月12日
  • 创建了问题 3月17日

悬赏问题

  • ¥60 pb数据库修改或者求完整pb库存系统,需为pb自带数据库
  • ¥15 spss统计中二分类变量和有序变量的相关性分析可以用kendall相关分析吗?
  • ¥15 拟通过pc下指令到安卓系统,如果追求响应速度,尽可能无延迟,是不是用安卓模拟器会优于实体的安卓手机?如果是,可以快多少毫秒?
  • ¥20 神经网络Sequential name=sequential, built=False
  • ¥16 Qphython 用xlrd读取excel报错
  • ¥15 单片机学习顺序问题!!
  • ¥15 ikuai客户端多拨vpn,重启总是有个别重拨不上
  • ¥20 关于#anlogic#sdram#的问题,如何解决?(关键词-performance)
  • ¥15 相敏解调 matlab
  • ¥15 求lingo代码和思路