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

AcWing-游戏

1388. 游戏 - AcWing题库

所需知识:博弈论,区间dp

由于双方都采取最优的策略来取数字,所以结果为确定的,有可能会有多个不同的过程,但是我们只需要关注最终结果就行了。

方法一:

定义dp[i][j] 表示区间i到j中先手能取得的最大值,依次遍历区间,最后判断最大值,因为区间长度长的来源必定是区间长度短的,所以我们可以第一层遍历区间的长度,第二层遍历区间的左端点。

状态转移方程式:dp[i][j]=max(w[i]+s[j]-s[i]-dp[i+1][j],w[j]+s[j-1]-s[i-1]-dp[i][j-1]);

对于状态转移方程式的解释:

若选择左边的数字,则,下一个人在i+1到j中选择对于他自己而言的最优解,所以,dp[i][j] 为w[i] +s[j]-s[i] (i+1到j的区间和) -dp[i+1][j](减去下一个人能拿的最大值)。

若选择右边的数字,则,下一个人在i到j-1中选择对于他自己而言的最优解,所以,dp[i][j] 为w[j] +s[j-1]-s[i-1] (i到j-1的区间和) -dp[i][j-1](减去下一个人能拿的最大值)。

最后取最大值,即为答案。

C++代码:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int N;
int dp[105][105];
int w[105],s[105];
int main()
{cin>>N;for (int i = 1; i <= N; i ++ ){cin>>w[i];s[i]=s[i-1]+w[i];}for(int len=1;len<=N;len++){for(int i=1;i<=N;i++){int j=i+len-1;dp[i][j]=max(w[i]+s[j]-s[i]-dp[i+1][j],w[j]+s[j-1]-s[i-1]-dp[i][j-1]);}}cout<<dp[1][N]<<' '<<s[N]-dp[1][N];return 0;
}

方法二:

定义dp[i][j] 表示在区间i到j内先手能拿到的最优值减去后手拿的最优值,即为A-B(A为方法一中的区间最大值,B为区间和减最大值);

遍历方法仍和方法一一样,先遍历一遍区间长度,然后再遍历左端点的值。

状态转移方程式:dp[i][j]=max(w[i]-dp[i+1][j],w[j]-dp[i][j-1]);

对于状态转移方程式的解释:

若取左边的数,则下一个人在区间i+1到j中取dp[i+1][j]表示该区间中的max(B-A),所以-dp[i+1][j]表示该区间中A-B的最大值,在加上w[i],表示区间i到j中A-B的最大值;

同理,若取右边的数,则下一个人在区间i到j-1中取dp[i][j-1]表示该区间中的max(B-A),所以-dp[i][j-1]表示该区间中A-B的最大值,在加上w[j],表示区间i到j中A-B的最大值;

最后dp[1][N]表示该区间内A-B的最大值,又因为A+B=sum(sum为所有元素和);

联立两个方程解得,A=(dp[1][N]+sum)/2;B=(sum-dp[1][N])/2;

C++代码:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int N;
int dp[105][105];
int w[105],s[105];
int sum=0;
int main()
{cin>>N;for (int i = 1; i <= N; i ++ ){cin>>w[i];sum+=w[i];}for(int len=1;len<=N;len++){for(int i=1;i+len-1<=N;i++){int j=i+len-1;dp[i][j]=max(w[i]-dp[i+1][j],w[j]-dp[i][j-1]);}}cout<<(sum+dp[1][N])/2<<' '<<(sum-dp[1][N])/2;return 0;
}

相关文章:

AcWing-游戏

1388. 游戏 - AcWing题库 所需知识&#xff1a;博弈论&#xff0c;区间dp 由于双方都采取最优的策略来取数字&#xff0c;所以结果为确定的&#xff0c;有可能会有多个不同的过程&#xff0c;但是我们只需要关注最终结果就行了。 方法一&#xff1a; 定义dp[i][j] 表示区间…...

Mybatis——一对一映射

一对一映射 预置条件 在某网络购物系统中&#xff0c;一个用户只能拥有一个购物车&#xff0c;用户与购物车的关系可以设计为一对一关系 数据库表结构&#xff08;唯一外键关联&#xff09; 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …...

Web 安全之 SSL 剥离攻击详解

目录 SSL/TLS简介 SSL 剥离攻击原理 SSL 剥离攻击的影响 SSL 剥离攻击的防范措施 小结 SSL 剥离攻击&#xff08;SSL Stripping Attack&#xff09;是一种针对安全套接层&#xff08;SSL&#xff09;或传输层安全性&#xff08;TLS&#xff09;协议的攻击手段&#xff0c;…...

数据结构——顺序表(C语言)

目录 一、顺序表概念 二、顺序表分类 1.静态顺序表 2.动态顺序表 三、顺序表的实现 1.顺序表的结构体定义 2. 顺序表初始化 3.顺序表销毁 4.顺序表的检验 5.顺序表打印 6.顺序表扩容 7.顺序表尾插与头插 8.尾删与头删 9.在pos处插入数据 10.在pos处删除数据 11.查找数据 …...

利用Idea实现Ajax登录(maven工程)

一、新建一个maven工程&#xff08;不会建的小伙伴可以参考Idea引入maven工程依赖(保姆级)-CSDN博客&#xff09;&#xff0c;工程目录如图 ​​​​​​​ js文件可以上up网盘提取 链接&#xff1a;https://pan.baidu.com/s/1yOFtiZBWGJY64fa2tM9CYg?pwd5555 提取码&…...

环信IM集成教程——Web端UIKit快速集成与消息发送

写在前面&#xff1a; 千呼万唤始出来&#xff0c;环信Web端终于出UIKit了&#xff01;&#x1f389;&#x1f389;&#x1f389; 文档地址&#xff1a;https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…...

Anaconda如何切换国内镜像源

一、anaconda如何切换阿里镜像源 在Anaconda中切换到阿里云镜像源可以通过以下步骤进行&#xff1a; 1、打开终端&#xff08;Windows&#xff09;或者命令行界面&#xff08;macOS/Linux&#xff09;。 2、执行以下命令来配置阿里云镜像源&#xff1a; conda config --add…...

Android 14.0 添加自定义服务,并生成jar给第三方app调用

1.概述 在14.0系统ROM产品定制化开发中,由于需要新增加自定义的功能,所以要增加自定义服务,而app上层通过调用自定义服务,来调用相应的功能,所以系统需要先生成jar,然后生成jar 给上层app调用,接下来就来分析实现的步骤,然后来实现相关的功能 从而来实现所需要的功能 …...

解决沁恒ch592单片机在tmos中使用USB总线时,接入USB Hub无法枚举频繁Reset的问题

开发产品时采用了沁恒ch592&#xff0c;做USB开发时遇到了一个奇葩的无法枚举问题。 典型症状 使用USB线直连电脑时没有问题&#xff0c;可以正常使用。 如果接入某些特定方案的USB Hub&#xff08;例如GL3510、GL3520&#xff09;&#xff0c;可能会出现以下2种情况&#xf…...

nvm保姆级安装使用教程

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 开发环境篇 ✨特色专栏&#xff1a; M…...

大语言模型LLM《提示词工程指南》学习笔记02

文章目录 大语言模型LLM《提示词工程指南》学习笔记02设计提示时需要记住的一些技巧零样本提示少样本提示链式思考&#xff08;CoT&#xff09;提示自我一致性生成知识提示 大语言模型LLM《提示词工程指南》学习笔记02 设计提示时需要记住的一些技巧 指令 您可以使用命令来指…...

【realme x2手机解锁BootLoader(简称BL)】

realme手机解锁常识 https://www.realme.com/cn/support/kw/doc/2031665 realme手机解锁支持型号 https://www.realmebbs.com/post-details/1275426081138028544 realme x2手机解锁实践 参考&#xff1a;https://www.realmebbs.com/post-details/1255473809142591488 1 下载apk…...

攻防世界 wife_wife

在这个 JavaScript 示例中&#xff0c;有两个对象&#xff1a;baseUser 和 user。 baseUser 对象定义如下&#xff1a; baseUser { a: 1 } 这个对象有一个属性 a&#xff0c;其值为 1&#xff0c;没有显式指定原型对象&#xff0c;因此它将默认继承 Object.prototype。 …...

Visual Studio安装下载进度为零已解决

因为在安装pytorch3d0.3.0时遇到问题&#xff0c;提示没有cl.exe&#xff0c;VS的C编译组件&#xff0c;可以添加组件也可以重装VS。查了下2019版比2022问题少&#xff0c;选择了安装2019版&#xff0c;下面是下载安装时遇到的问题记录&#xff0c;关于下载进度为零网上有三类解…...

矩阵空间秩1矩阵小世界图

文章目录 1. 矩阵空间2. 微分方程3. 秩为1的矩阵4. 图 1. 矩阵空间 我们以3X3的矩阵空间 M 为例来说明相关情况。目前矩阵空间M中只关心两类计算&#xff0c;矩阵加法和矩阵数乘。 对称矩阵-子空间-有6个3X3的对称矩阵&#xff0c;所以为6维矩阵空间上三角矩阵-子空间-有6个3…...

《QT实用小工具·十三》FlatUI辅助类之各种炫酷的控件集合

1、概述 源码放在文章末尾 FlatUI辅助类之各种炫酷的控件集合 按钮样式设置。文本框样式设置。进度条样式。滑块条样式。单选框样式。滚动条样式。可自由设置对象的高度宽度大小等。自带默认参数值。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; #ifnd…...

dm8 备份与恢复

dm8 备份与恢复 基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…...

Vue项目中引入html页面(vue.js中引入echarts数据大屏html [静态非数据传递!] )

在项目原有vue&#xff08;例如首页&#xff09;基础上引入html页面 1、存放位置 vue3原有public文件夹下 我这边是新建一个static文件夹 专门存放要用到的html文件 复制拖拽过来 index为html的首页 2、更改路径引入到vue中 这里用到的是 iframe 方法 不同于vue的 component…...

ASTM C1186-22 纤维水泥平板

以无石棉类无机矿物纤维、有机合成纤维或纤维素纤维&#xff0c;单独或混合作为增强材料&#xff0c;以普通硅酸盐水泥或水泥中添加硅质、钙质材料代替部分水泥为胶凝材料&#xff0c;经制浆、成型、蒸汽或高压蒸汽养护制成的板材&#xff0c;俗称水泥压力板。 ASTM C1186-22纤…...

NoSQL概述

NoSQL概述 目录 一、为什么用NoSQL 二、什么是NoSQL 三、经典应用分析 四、N o S Q L 数 据 模 型 简 介 五、NoSQL四大分类 六、CAP BASE 一、为什么用NoSQL 1、单机MySQL的美好年代 在90年代&#xff0c;一个网站的访问量一般不大&#xff0c;用单个数据库完全可以轻松应…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...