Acwing.1388 游戏(区间DP对抗思想)
题目
玩家一和玩家二共同玩一个小游戏。
给定一个包含 N个正整数的序列。
由玩家一开始,双方交替行动。
每次行动可以在数列的两端之中任选一个数字将其取走,并给自己增加相应数字的分数。(双初始分都是 0分)
当所有数字都被取完时,游戏结束。
分更高的一方获胜。
请计算,如果双方都采取最优策略进行游戏,则游戏结束时,双方的得分各是多少。
输入格式
第一行包含整数 N。
后面若干行包含 N个整数,表示这个序列。注意每行不一定恰好包含一个数。
输出格式
共一行,两个整数,分别表示玩家一和玩家二的最终得分。
数据范围
2≤N≤100
数列中的数字的取值范围为 [1,200]
- 输入样例:
6
4 7 2 9
5 2
- 输出样例:
18 11
题解
import java.util.Scanner;/*** @author akuya* @create 2024-04-03-18:47*/
public class Main {static int N=105;static int n;static int w[]=new int[N];static int f[][]=new int[N][N];public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();for(int i=0;i<n;i++){w[i]=scanner.nextInt();}for(int len=1;len<=n;len++){for(int i=0;i+len-1<n;i++){int j=i+len-1;if(len==1)//区间长度为1则只有一个可拿。f[i][j]=w[i];elsef[i][j]=Math.max(w[i]-f[i+1][j],w[j]-f[i][j-1]);}}int sum=0,d=f[0][n-1];for(int i=0;i<n;i++) sum+=w[i];//A+B=SUM A-B=d//A=SUM-D/2//B=SUM-D/2System.out.println((sum+d)/2+" "+(sum-d)/2);}
}
思路
首先这道题用的是区间DP,区间DP与背包问题一样有具体的模板,第一层遍历区间长度,第二层遍历左端点。dp数组的两个元素也利索当然得是区间的两个端点。
这道题是一道经典的对抗问题,要求比较谁更高,也就是使自己的分数与对方的分数的分差更大,因此dp数组为选择i到j区间里分差最大的选择。在每第i-j区域的选择里,我们可以从左或者从右选,在这次选择之前是对方选择,对方肯定会选择对自己更优的方案,也就是使自己方差和我们方差最大的方案,设为a(a=f[i+1][j]orf[i][j-1])。那么在这次选择之前,我们与对方的方差是-a。我们需要在这样的前提情况下选择与对方方差最大的方案,也就是-a+左或者-a加上右。
完成以上逻辑即可解答出本题。
相关文章:
Acwing.1388 游戏(区间DP对抗思想)
题目 玩家一和玩家二共同玩一个小游戏。 给定一个包含 N个正整数的序列。 由玩家一开始,双方交替行动。 每次行动可以在数列的两端之中任选一个数字将其取走,并给自己增加相应数字的分数。(双初始分都是 0分) 当所有数字都被…...
Numpy数组转换为csv文件
参考:Converting Numpy Array to CSV 在数据分析和处理中,经常会涉及到将数据从一个形式转换为另一个形式的操作。 其中,将Numpy数组转换为csv文件是一种常见的操作,因为csv文件是一种通用的数据存储格式,方便与其他软…...
替代安全指标(Surrogate Safety Measures (SSM) )
替代安全措施(Surrogate Safety Measures (SSM) )用于从数据中寻找接近碰撞,或可能发生(但实际没有发生)的碰撞事件。 SSM的两个合格标准: (1)它应该来自与碰撞直接相关的交通冲突&…...
usb_camera传输视频流编码的问题记录!
前言: 大家好,今天给大家分享的内容是,一个vip课程付费的朋友,在学习过程中遇到了一个usb采集的视频数据流,经过ffmpeg编码,出现了问题: 问题分析: 其实这个问题不难,关键…...
Linux安装nginx保姆级教程
文章目录 前言一、nginx安装(保姆级教程)1.安装nginx依赖2.安装wget3.创建nginx安装目录4.下载nginx5.查看下载好的nginx6.解压缩7.查看当前目录下的文件→进入nginx-1.8.0目录→查看当前目录下的文件8.安装nginx9.查看nginx安装目录并启动nginx10.网络请…...
leetcode-判断二分图
. - 力扣(LeetCode) 存在一个 无向图 ,图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ,其中 graph[u] 是一个节点数组,由节点 u 的邻接节点组成。形式上,…...
算法day30 回溯6
332 重新安排行程 给你一份航线列表 tickets ,其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK …...
分享three.js实现乐高小汽车
前言 Web脚本语言JavaScript入门容易,但是想要熟练掌握却需要几年的学习与实践,还要在弱类型开发语言中习惯于使用模块来构建你的代码,就像小时候玩的乐高积木一样。 应用程序的模块化理念,通过将实现隐藏在一个简单的接口后面&a…...
gpt的构造和原理
gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的!比如“Q:xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中,文本序列(可能包含问题和紧随其后的答案)被视为一个整体输入到模型…...
基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展,计算机的应用日渐成熟,其强大的功能给人们留下深刻的印象,它已经应用到了人类社会的各个层次的领域,发挥着重要的不可替换的作用。信息管理作为计算…...
K8S之Job和CronJob控制器
这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务,例如:对数据库备份,可以直接在k8s上启动一个mysqldump备份程序,也可以启动一个pod,这个pod…...
基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。
演示视频: 基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构&…...
哈佛大学商业评论 --- 第三篇:真实世界中的增强现实
AR将全面融入公司发展战略! AR将成为人类和机器之间的新接口! AR将成为人类的关键技术之一! 请将此文转发给您的老板! --- 本文作者:Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的,但大…...
华为ICT七力助推文化产业新质生产力发展
创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成,符合新发展理念的先进生产力质态;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能,新质生产力能够摆脱…...
FastGpt流程
1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本,在文本里面进行数据清洗(以防知识库删除后,数据清洗失效) 可以插图,将图片通过网页检查F12查看路径放进去 或者直接在csdn放,直接复制链接…...
怎么在UE游戏中加入原生振动效果
我是做振动触感的。人类的五感“视听嗅味触”,其中的“触”就是触觉,是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯,也是习以为常,很多人漠视了触感的价值。大家对触感的认知还远远不…...
【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】
前言: 💞💞大家好,我是书生♡,今天的内容主要是Hadoop的后两个组件:MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 💞💞前路漫漫&…...
蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)
题目描述 给定一个数组 Ai,分别求其每个子段的异或和,并求出它们的和。 或者说,对于每组满足 1≤L≤R≤n 的 L,R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L,R 得到的结果加起来的值。 输入格式 输入…...
background背景图参数边渐变CSS中创建背景图像的渐变效果
效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变(linear-gradient)或径向渐变(radial-gradient)。以下是一个使用线性渐变作为背景图像 代码: background: linear-gradient(to top, rgba(255,255,255,0)…...
『大模型笔记』吴恩达:AI 智能体工作流引领人工智能新趋势
吴恩达:AI 智能体工作流引领人工智能新趋势 文章目录 一. 概述二. AI 智能体的设计模式2.1. 反思(Reflection)2.2. 使用工具(Tool use)2.3. 规划(Planning)2.4. 多智能体协作(Multi-agent collaboration)三. 最后总结四. 参考文献一. 概述 我期待与大家分享我在 AI 智能体方面…...
腾讯光子工作室群 一面 (30min)
问题: 你毕业是打算考研还是直接工作 深挖项目(介绍、剖析遇到问题如何解决): 你在进行攻击的时候会不会有穿模的情况,怎么解决 为什么会造成卡顿(多嘴说的) 说说行为树和状态机之间的差别 …...
Linux的信号栈的实现(1)
作者 pengdonglin137@163.com 环境 Linux 6.5 + ARM64 概述 在前一篇文章中介绍了Linux系统中的几种栈以及它们之间的切换,进程在用户态和内核态会使用不同的栈,在用户态的主线程和其他线程都有各自的栈,此外进程在执行信号处理程序时也需要栈,那么这个栈来自哪呢? …...
Python学习笔记——heapq
堆排序 思路 堆排序思路是: 将数组以二叉树的形式分析,令根节点索引值为0,索引值为index的节点,子节点索引值分别为index*21、index*22;对二叉树进行维护,使得每个非叶子节点的值,都大于或者…...
搜索与图论——拓扑排序
有向图的拓扑排序就是图的宽度优先遍历的一个应用 有向无环图一定存在拓扑序列(有向无环图又被称为拓扑图),有向有环图一定不存在拓扑序列。无向图没有拓扑序列。 拓扑序列:将一个图排成拓扑序后,所有的边都是从前指…...
linux CentOS7配置docker的yum源并安装
[TOC](这里写目录标题 配置yum源Docker的自动化安装一些其他启动相关的命令: 配置yum源 使用以下命令下载CentOS官方的yum源文件 wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 清除yum缓存 yum clean all 更新yum缓存…...
vue结合Elempent-Plus/UI穿梭框更改宽度以及悬浮文本显示
由于分辨率不同会导致文本内容显示不全,如下所示: 因此需要 1、悬浮到对应行上出现悬浮信息 实现代码如下所示: 这里只演示Vue3版本代码,Vue2版本不再演示 区别就在插槽使用上Vue3使用:#default“”;Vu…...
汇川PLC学习Day4:电机参数和气缸控制参数
汇川PLC学习Day4:伺服电机参数和气缸控制参数 一、伺服电机参数二、气缸参数1. 输入IO映射(1)输入IO映射(2) 输入IO触摸屏标签显示映射 2. 输出IO映射(1)输出IO映射(2) …...
数据可视化高级技术Echarts(快速上手柱状图进阶操作)
目录 1.Echarts的配置 2.程序的编码 3.柱状图的实现(入门实现) 相关属性介绍(进阶): 1.标记最大值/最小值 2.标记平均值 3.柱的宽度 4. 横向柱状图 5.colorBy series系列(需要构造多组数据才能实现…...
【数据结构与算法】力扣 206. 反转链表
题目描述 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 输入: head [1,2,3,4,5] 输出: [5,4,3,2,1]示例 2: 输入: head [1,2] 输出: [2,1]示例 3&#…...
【随笔】Git 高级篇 -- 本地栈式提交 rebase | cherry-pick(十七)
💌 所属专栏:【Git】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! 💖 欢迎大…...
wordpress 3.9.2 下载/免费入驻的卖货平台有哪些
本篇介绍C语言中关键字extern。实现使多个脚本文件共享使用在某个脚本文件中已经定义声明的变量和函数。 ExternTest.cpp脚本文件 /* * Author:W * 关于extern关键字作用测试类 */ //引入头文件:头文件包含了程序中必需的或有用的信息 #include <iostream> …...
一个网站做app/百度的seo关键词优化怎么弄
目录 视频教程环境信息相关服务NFS服务部署创建kibana的配置文件创建pv创建pvc创建kibana服务验证视频教程 视频教程:https://edu.csdn.net/learn/38191/604467?spm=1003.2001.3001.4143 环境信息 相关服务 服务版本elasticsearch7.1.1kibana7.1.1rancher2.4.3NFS服务 服…...
采集做网站/佛山百度推广公司
一、简介 vim 是 Linux 下常使用的一款文本编辑器。如果你是初识 vim 的话,一定会对其五花八门的快捷键和命令感到头晕。 所以,这里介绍一些 vim 下使用频率较高的命令,掌握这些基本也够,至于其它更多的命令介绍,以后还…...
wordpress 分页url/徐州seo公司
原文:http://blog.csdn.net/liaokailin/article/details/48186331 spring boot实战(第二篇)事件监听 前言 spring boot在启动过程中增加事件监听机制,为用户功能拓展提供极大的便利。 支持的事件类型四种 ApplicationStartedEvent ApplicationEnvironmentPreparedEv…...
网站建设重要意义/汉中seo培训
工业触摸屏一体机-迅为7寸触控一体机工业人机界面_安卓触摸屏,适用于自动售货机、人机界面、自动终端、广告机、触摸控制系统 接口支持:全网通4G模块、WIFI蓝牙模块、千兆以太网、CAN总线、RS-485模块 系统支持:Android4.4/5.1安卓系统 CPU处…...
稿定设计免费模板/凯里seo排名优化
一、下载系统镜像文件 首先下载系统镜像,进入kali官网,在Downloads中选择Download Kali Linux,如下图所示。 2.根据电脑配置选择合适的版本,在这里我选择的是64位版本,点击HTTP下载镜像文件,或者torrent下…...