当前位置: 首页 > 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 智能体方面…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space

问题&#xff1a;IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案&#xff1a;将编译的堆内存增加一点 位置&#xff1a;设置setting-》构建菜单build-》编译器Complier...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...