当前位置: 首页 > news >正文

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个正整数的序列。 由玩家一开始&#xff0c;双方交替行动。 每次行动可以在数列的两端之中任选一个数字将其取走&#xff0c;并给自己增加相应数字的分数。&#xff08;双初始分都是 0分&#xff09; 当所有数字都被…...

Numpy数组转换为csv文件

参考&#xff1a;Converting Numpy Array to CSV 在数据分析和处理中&#xff0c;经常会涉及到将数据从一个形式转换为另一个形式的操作。 其中&#xff0c;将Numpy数组转换为csv文件是一种常见的操作&#xff0c;因为csv文件是一种通用的数据存储格式&#xff0c;方便与其他软…...

替代安全指标(Surrogate Safety Measures (SSM) )

替代安全措施&#xff08;Surrogate Safety Measures (SSM) &#xff09;用于从数据中寻找接近碰撞&#xff0c;或可能发生&#xff08;但实际没有发生&#xff09;的碰撞事件。 SSM的两个合格标准&#xff1a; &#xff08;1&#xff09;它应该来自与碰撞直接相关的交通冲突&…...

usb_camera传输视频流编码的问题记录!

前言&#xff1a; 大家好&#xff0c;今天给大家分享的内容是&#xff0c;一个vip课程付费的朋友&#xff0c;在学习过程中遇到了一个usb采集的视频数据流&#xff0c;经过ffmpeg编码&#xff0c;出现了问题&#xff1a; 问题分析&#xff1a; 其实这个问题不难&#xff0c;关键…...

Linux安装nginx保姆级教程

文章目录 前言一、nginx安装&#xff08;保姆级教程&#xff09;1.安装nginx依赖2.安装wget3.创建nginx安装目录4.下载nginx5.查看下载好的nginx6.解压缩7.查看当前目录下的文件→进入nginx-1.8.0目录→查看当前目录下的文件8.安装nginx9.查看nginx安装目录并启动nginx10.网络请…...

leetcode-判断二分图

. - 力扣&#xff08;LeetCode&#xff09; 存在一个 无向图 &#xff0c;图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph &#xff0c;其中 graph[u] 是一个节点数组&#xff0c;由节点 u 的邻接节点组成。形式上&#xff0c…...

算法day30 回溯6

332 重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必须从 JFK …...

分享three.js实现乐高小汽车

前言 Web脚本语言JavaScript入门容易&#xff0c;但是想要熟练掌握却需要几年的学习与实践&#xff0c;还要在弱类型开发语言中习惯于使用模块来构建你的代码&#xff0c;就像小时候玩的乐高积木一样。 应用程序的模块化理念&#xff0c;通过将实现隐藏在一个简单的接口后面&a…...

gpt的构造和原理

gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的&#xff01;比如“Q&#xff1a;xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中&#xff0c;文本序列&#xff08;可能包含问题和紧随其后的答案&#xff09;被视为一个整体输入到模型…...

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…...

K8S之Job和CronJob控制器

这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务&#xff0c;例如&#xff1a;对数据库备份&#xff0c;可以直接在k8s上启动一个mysqldump备份程序&#xff0c;也可以启动一个pod&#xff0c;这个pod…...

基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的基于个人需求和地域特色的外卖推荐系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…...

哈佛大学商业评论 --- 第三篇:真实世界中的增强现实

AR将全面融入公司发展战略&#xff01; AR将成为人类和机器之间的新接口&#xff01; AR将成为人类的关键技术之一&#xff01; 请将此文转发给您的老板&#xff01; --- 本文作者&#xff1a;Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的&#xff0c;但大…...

华为ICT七力助推文化产业新质生产力发展

创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成&#xff0c;符合新发展理念的先进生产力质态&#xff1b;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能&#xff0c;新质生产力能够摆脱…...

FastGpt流程

1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本&#xff0c;在文本里面进行数据清洗&#xff08;以防知识库删除后&#xff0c;数据清洗失效&#xff09; 可以插图&#xff0c;将图片通过网页检查F12查看路径放进去 或者直接在csdn放&#xff0c;直接复制链接…...

怎么在UE游戏中加入原生振动效果

我是做振动触感的。人类的五感“视听嗅味触”&#xff0c;其中的“触”就是触觉&#xff0c;是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯&#xff0c;也是习以为常&#xff0c;很多人漠视了触感的价值。大家对触感的认知还远远不…...

【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】

前言&#xff1a; &#x1f49e;&#x1f49e;大家好&#xff0c;我是书生♡&#xff0c;今天的内容主要是Hadoop的后两个组件&#xff1a;MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 &#x1f49e;&#x1f49e;前路漫漫&…...

蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)

题目描述 给定一个数组 Ai&#xff0c;分别求其每个子段的异或和&#xff0c;并求出它们的和。 或者说&#xff0c;对于每组满足 1≤L≤R≤n 的 L&#xff0c;R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L&#xff0c;R 得到的结果加起来的值。 输入格式 输入…...

background背景图参数边渐变CSS中创建背景图像的渐变效果

效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变&#xff08;linear-gradient&#xff09;或径向渐变&#xff08;radial-gradient&#xff09;。以下是一个使用线性渐变作为背景图像 代码: 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 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

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

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

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

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 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);…...