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题库 所需知识:博弈论,区间dp 由于双方都采取最优的策略来取数字,所以结果为确定的,有可能会有多个不同的过程,但是我们只需要关注最终结果就行了。 方法一: 定义dp[i][j] 表示区间…...

Mybatis——一对一映射
一对一映射 预置条件 在某网络购物系统中,一个用户只能拥有一个购物车,用户与购物车的关系可以设计为一对一关系 数据库表结构(唯一外键关联) 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …...
Web 安全之 SSL 剥离攻击详解
目录 SSL/TLS简介 SSL 剥离攻击原理 SSL 剥离攻击的影响 SSL 剥离攻击的防范措施 小结 SSL 剥离攻击(SSL Stripping Attack)是一种针对安全套接层(SSL)或传输层安全性(TLS)协议的攻击手段,…...
数据结构——顺序表(C语言)
目录 一、顺序表概念 二、顺序表分类 1.静态顺序表 2.动态顺序表 三、顺序表的实现 1.顺序表的结构体定义 2. 顺序表初始化 3.顺序表销毁 4.顺序表的检验 5.顺序表打印 6.顺序表扩容 7.顺序表尾插与头插 8.尾删与头删 9.在pos处插入数据 10.在pos处删除数据 11.查找数据 …...

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

环信IM集成教程——Web端UIKit快速集成与消息发送
写在前面: 千呼万唤始出来,环信Web端终于出UIKit了!🎉🎉🎉 文档地址:https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…...

Anaconda如何切换国内镜像源
一、anaconda如何切换阿里镜像源 在Anaconda中切换到阿里云镜像源可以通过以下步骤进行: 1、打开终端(Windows)或者命令行界面(macOS/Linux)。 2、执行以下命令来配置阿里云镜像源: conda config --add…...
Android 14.0 添加自定义服务,并生成jar给第三方app调用
1.概述 在14.0系统ROM产品定制化开发中,由于需要新增加自定义的功能,所以要增加自定义服务,而app上层通过调用自定义服务,来调用相应的功能,所以系统需要先生成jar,然后生成jar 给上层app调用,接下来就来分析实现的步骤,然后来实现相关的功能 从而来实现所需要的功能 …...

解决沁恒ch592单片机在tmos中使用USB总线时,接入USB Hub无法枚举频繁Reset的问题
开发产品时采用了沁恒ch592,做USB开发时遇到了一个奇葩的无法枚举问题。 典型症状 使用USB线直连电脑时没有问题,可以正常使用。 如果接入某些特定方案的USB Hub(例如GL3510、GL3520),可能会出现以下2种情况…...

nvm保姆级安装使用教程
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 开发环境篇 ✨特色专栏: M…...
大语言模型LLM《提示词工程指南》学习笔记02
文章目录 大语言模型LLM《提示词工程指南》学习笔记02设计提示时需要记住的一些技巧零样本提示少样本提示链式思考(CoT)提示自我一致性生成知识提示 大语言模型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手机解锁实践 参考:https://www.realmebbs.com/post-details/1255473809142591488 1 下载apk…...

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

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

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

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

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

Vue项目中引入html页面(vue.js中引入echarts数据大屏html [静态非数据传递!] )
在项目原有vue(例如首页)基础上引入html页面 1、存放位置 vue3原有public文件夹下 我这边是新建一个static文件夹 专门存放要用到的html文件 复制拖拽过来 index为html的首页 2、更改路径引入到vue中 这里用到的是 iframe 方法 不同于vue的 component…...
ASTM C1186-22 纤维水泥平板
以无石棉类无机矿物纤维、有机合成纤维或纤维素纤维,单独或混合作为增强材料,以普通硅酸盐水泥或水泥中添加硅质、钙质材料代替部分水泥为胶凝材料,经制浆、成型、蒸汽或高压蒸汽养护制成的板材,俗称水泥压力板。 ASTM C1186-22纤…...

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

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

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 问题
报错: 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 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 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 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...