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年代,一个网站的访问量一般不大,用单个数据库完全可以轻松应…...
爬虫实战一、Scrapy开发环境(Win10+Anaconda3)搭建
#前言 在这儿推荐使用Anaconda进行安装,并不推荐大家用pythonpip安装,因为pythonpip的坑实在是太多了。 #一、环境中准备: Win10(企业版)Anaconda3-5.0.1-Windows-x86_64,下载地址,如果打不开…...
llama.cpp运行qwen0.5B
编译llama.cp 参考 下载模型 05b模型下载 转化模型 创建虚拟环境 conda create --prefixD:\miniconda3\envs\llamacpp python3.10 conda activate D:\miniconda3\envs\llamacpp安装所需要的包 cd G:\Cpp\llama.cpp-master pip install -r requirements.txt python conver…...
【接口】HTTP(3) |GET和POST两种基本请求方法有什么区别
在我面试时,在我招人面试别人时,10次能遇到7次这个问题,我听过我也说回答过: Get: 一般对于从服务器取数据的请求可以设置为get方式 Get方式在传递参数的时候,一般都会把参数直接拼接在url上 Get请求方法…...
金陵科技学院软件工程学院软件工程专业
感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦…...
Android 关于apk反编译d2j-dex2jar classes.dex失败的几种方法
目录 确认路径正确直接定位到指定目录确定目录正确,按如下路径修改下面是未找到相关文件正确操作 确认路径正确 ,即d2j-dex2jar和classes.dex是否都在一个文件夹里(大部分的情况都是路径不正确) 直接定位到指定目录 路径正确的…...
Django--admin 后台管理站点
Django最大的优点之一,就是体贴的提供了一个基于项目model创建的一个后台管理站点admin。这个界面只给站点管理员使用,并不对大众开放。虽然admin的界面可能不是那么美观,功能不是那么强大,内容不一定符合你的要求,但是…...
JavaScript(六)---【回调、异步、promise、Async】
零.前言 JavaScript(一)---【js的两种导入方式、全局作用域、函数作用域、块作用域】-CSDN博客 JavaScript(二)---【js数组、js对象、this指针】-CSDN博客 JavaScript(三)---【this指针,函数定义、Call、Apply、函数绑定、闭包】-CSDN博客 JavaScript(四)---【执…...
vue2+elementUi的两个el-date-picker日期组件进行联动
vue2elementUi的两个el-date-picker日期组件进行联动 <template><el-form><el-form-item label"起始日期"><el-date-picker v-model"form.startTime" change"startTimeChange" :picker-options"startTimePickerOption…...
GIN实例讲解
第一个gin程序 package mainimport ("github.com/gin-gonic/gin" )func main() {// 创建一个 Gin 引擎实例r : gin.Default()// 定义一个 GET 请求的路由,当访问 /hello 路径时执行匿名函数r.GET("/hello", func(c *gin.Context) {// 获取查询…...
开源充电桩设备监控系统技术解决方案
开源 | 慧哥充电桩平台V2.5.2(支持 汽车 电动自行车 云快充1.5、云快充1.6 微服务 ) SpringBoot设备监控系统解决方案 一、引言 1.项目背景 随着物联网技术的快速发展,设备的智能化和网络化程度日益提高。在现代工业和信息化的背景下&#x…...
服装批发网站建设/沪深300指数是什么意思
psutil模块 1.介绍 psutil是一个跨平台库(http://code.google.com/p/psutil/),能够轻松实现获取系统运行的进程和系统利用率(包括CPU、内存、磁盘、网络等)信息。它主要应用于系统监控,分析和限制系统资源及…...
企业网站的常见类型有/58同城安居客
查看变量:mysql -pshow variables;或者mysql -uroot -p variables |grep max_connections显示当前运行的Query:mysql> show processlist;显示当前状态:mysql> show status;修改MYSQL最大连接数的3种方…...
wordpress文章后缀/企业网站开发公司
创建Windows服务来运行批处理任务或者运行后台任务,是一种非常常见的模式,但是由于云服务(Amazon Lambda, Azure WebJobs以及Azure Functions)的激增,你可能不会经常使用Windows服务了。个人而言,我非常喜欢…...
.cn和.net网站是一样吗/友情链接怎么交换
2019独角兽企业重金招聘Python工程师标准>>> 在一个项目中要生成验证码,用ExtJs 4.2实现。最常见的验证码就是一个输入框和一个验证码图片。 第一个感觉就是用Ext.container.Container将textfield和img放进去。所以,有了以下的代码࿱…...
外星人做的网站/百度公司网站推广怎么做
在网上找的例子,可以参考一些 create table examples(names varchar(10 ),age number(3 ),BirDate date default sysdate)执行insert时,只需要insert前两个字段,BirDate字段会自动用当前时间填充,如下: insert into example…...
wordpress 数据库 媒体库/时空seo助手
Citrix 服务器虚拟化之十七 桌面虚拟化之准备虚拟桌面模版 XenDesktop 7.0已经支持Windows 8及Windows Server 2012了。 说明: 环境基于实验十六 1、准备一台Windows 8的虚拟机名为Windows8-1,然后安装Xenserver-Tools,接着加入域kkfloat.com,IP地址设置…...