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 智能体方面…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...

6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...