9717 取数对弈

首先,我们需要初始化两个数组,一个用于存储输入的数列`a[]`,另一个用于动态规划过程中存储中间结果的二维数组`dp[][]`。`dp[i][j]`表示从数列的第`i`个数到第`j`个数时,当前玩家(甲方先手)能够获得的最大得分。

接下来,我们按照以下步骤进行动态规划:

1. 初始化`dp[i][i]`为`a[i]`,因为如果数列中只有一个数,当前玩家只能取这一个数。
2. 计算所有可能的数列长度(从2开始到n),对于每个长度,计算所有可能的起始位置i(从1到n-length+1)。
3. 对于每个起始位置i,计算结束位置j(i+length-1),然后根据动态规划的状态转移方程更新`dp[i][j]`。
4. 状态转移方程为:`dp[i][j] = sum(i,j) - min(dp[i+1][j], dp[i][j-1])`,其中`sum(i,j)`是从第i个数到第j个数的总和,可以通过前缀和数组预先计算以优化时间复杂度。
5. 最终,`dp[1][n]`就是甲方在最优策略下能获得的最大得分,乙方的得分则为总和减去`dp[1][n]`。

下面是具体的C++实现代码:

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> a(n+1);vector<vector<int>> dp(n+1, vector<int>(n+1));vector<int> sum(n+1, 0); // 前缀和数组// 读入数列并计算前缀和for (int i = 1; i <= n; ++i) {cin >> a[i];sum[i] = sum[i-1] + a[i];}// 初始化dp数组for (int i = 1; i <= n; ++i) {dp[i][i] = a[i];}// 动态规划计算dp数组for (int length = 2; length <= n; ++length) {for (int i = 1; i <= n - length + 1; ++i) {int j = i + length - 1;int total = sum[j] - sum[i-1]; // 计算当前数列的总和dp[i][j] = total - min(dp[i+1][j], dp[i][j-1]);}}// 输出甲乙双方的得分cout << dp[1][n] << " " << (sum[n] - dp[1][n]) << endl;return 0;
}

这段代码首先读取数列的长度和数列本身,然后计算前缀和以便快速计算任意子数列的总和。接着,通过动态规划填充`dp`数组,最后输出甲乙双方的得分。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/374789.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JavaScript(9)——作用域的一些问题

如果在函数内部&#xff0c;变量没有声明直接赋值&#xff0c;也会当做全局变量看。强烈不推荐&#xff01;&#xff01; function op() {num 80}op()console.log(num) 在不同作用域下&#xff0c;可能存在变量命名冲突的情况&#xff1a; let num 10 function fn(){let num…

前端如何取消接口调用

&#x1f9d1;‍&#x1f4bb; 写在开头 点赞 收藏 学会&#x1f923;&#x1f923;&#x1f923; 1. xmlHttpRequest是如何取消请求的&#xff1f; 实例化的XMLHttpRequest对象上也有abort方法 const xhr new XMLHttpRequest(); xhr.addEventListener(load, function(e)…

模式物种葡萄基因组(T2T)--文献精读29

The complete reference genome for grapevine (Vitis vinifera L.) genetics and breeding 葡萄&#xff08;Vitis vinifera L.&#xff09;遗传学和育种的完整参考基因组 摘要 葡萄是全球最具经济重要性的作物之一。然而&#xff0c;以往版本的葡萄参考基因组通常由成千上万…

关于centos7自带的nginx1.20.1开启https后,XP系统的IE6和IE8无法显示网页的问题

CentOS7自带的nginx-1.20.1是支持HTTP/2和TLS1.3的。 软件包名称&#xff1a;nginx-1.20.1-10.el7.x86_64 CentOS7默认开启了HTTP/2&#xff0c;但没有开启TLS1.3&#xff0c;以及IE6和IE8的https访问。 开启方法&#xff1a; ssl_ciphers HIGH:!aNULL:!MD5;改为ssl_ciphers…

防火墙第一次综合实验

DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问。 办公区设备10.8.2.1不允许访问DMZ区的FTP服务器和HTTP服务器&#xff0c;仅能ping通10.0.3.10 1.先建立拒绝BG到DMZ区的安全策略 2.建立BG到DMZ区的icmp允许 3…

网络基础:Vlan原理与配置

VLAN&#xff08;Virtual Local Area Network&#xff0c;虚拟局域网&#xff09;是一种将一个物理网络划分为多个逻辑子网的技术。它通过在网络交换机上配置&#xff0c;使得不同VLAN中的设备即使连接在同一个物理交换机上&#xff0c;也不能直接进行通信&#xff0c;从而实现…

系统服务综合作业01

题目&#xff1a; 现有主机 node01 和 node02&#xff0c;完成如下需求&#xff1a; 1、在 node01 主机上提供 DNS 和 WEB 服务 2、dns 服务提供本实验所有主机名解析 3、web服务提供 www.rhce.com 虚拟主机 4、该虚拟主机的documentroot目录在 /nfs/rhce 目录 5、该目录由 no…

三分钟看懂马尔可夫链(Markov Chain)是什么

马尔可夫链&#xff08;Markov Chain&#xff09;是一种数学模型&#xff0c;用于描述系统在不同状态之间的转移过程。简单来说&#xff0c;马尔可夫链描述了一个系统在各个状态之间转移的概率&#xff0c;这种转移是随机的&#xff0c;但遵循特定的概率规则。它有两个重要特性…

Linux shell编程学习笔记63:free命令 获取内存使用信息

0 前言 在系统安全检查中&#xff0c;内存使用情况也是一块可以关注的内容。Linux提供了多个获取内存信息的命令很多。今天我们先研究free命令。 1 free命令的功能、用法和选项说明 1.1 free命令的功能 free 命令可以显示系统内存的使用情况&#xff0c;包括物理内存、交换…

在Linux下使用Docker部署chirpstack

目录 一、前言 二、chirpstack 1、chirpstack是什么 2、chirpstack组件 3、为什么选择Docker部署 三、Linux下部署过程 四、web界面部署过程 一、前言 本篇文章我是在Linux下使用 Docker 进行部署chirpstack&#xff0c;chirpstack采用的是v4 版本&#xff0c;v4 版本 与…

Windows电脑安装Python结合内网穿透轻松搭建可公网访问私有网盘

文章目录 前言1.本地文件服务器搭建1.1.Python的安装和设置1.2.cpolar的安装和注册 2.本地文件服务器的发布2.1.Cpolar云端设置2.2.Cpolar本地设置 3.公网访问测试4.结语 前言 本文主要介绍如何在Windows系统电脑上使用python这样的简单程序语言&#xff0c;在自己的电脑上搭建…

阿里云RDS云数据库库表恢复操作

最近数据库中数据被人误删了,记录一下恢复操作方便以后发生时进行恢复. 1.打开控制台&#xff0c;进入云数据库实例. 2.进入实例后 &#xff0c;点击右侧的备份恢复&#xff0c;然后看一下备份时间点&#xff0c;中间这边都是阿里云自动备份的备份集&#xff0c;基本都是7天一备…

代发考生战报:南京考场华为售前HCSP H19-411考试通过

代发考生战报&#xff1a;南京考场华为售前HCSP H19-411考试通过&#xff0c;客服给的题库非常稳定&#xff0c;考试遇到2个新题&#xff0c;剩下全是题库里的原题&#xff0c;想考的放心考吧&#xff0c;考场服务挺好&#xff0c;管理员带着做签名和一些考试说明介绍清楚&…

【活动行】参与上海两场线下活动,教育生态行业赛总决赛活动和WAIC人工智能大会活动 - 上海活动总结

目录 背景决赛最后一公里领域范围 决赛作品AI智教相机辅导老师Copilot辅导老师Copilot雅思写作竞技场 优秀作品总结 背景 决赛 百度发起的千帆杯教育生态行业赛于2024年7月4日进行线下决赛&#xff0c;博主虽然没能进入决赛&#xff0c;但也非常荣幸能够以嘉宾身份到现场给进…

从0-1搭建一个web项目(页面布局详解)详解

本章分析页面布局详解详解 ObJack-Admin一款基于 Vue3.3、TypeScript、Vite3、Pinia、Element-Plus 开源的后台管理框架。在一定程度上节省您的开发效率。另外本项目还封装了一些常用组件、hooks、指令、动态路由、按钮级别权限控制等功能。感兴趣的小伙伴可以访问源码点个赞 地…

哈弗架构和冯诺伊曼架构

文章目录 1. 计算机体系结构 2. 哈弗架构&#xff08;Harvard Architecture&#xff09; 3. 改进的哈弗架构 4. 冯诺伊曼架构&#xff08;Von Neumann Architecture&#xff09; 5. 结构对比 1. 计算机体系结构 计算机体系结构是指计算机系统的组织和实现方式&#xff0c…

[终端安全]-7 后量子密码算法

本文参考资料来源&#xff1a;NSA Releases Future Quantum-Resistant (QR) Algorithm Requirements for National Security Systems > National Security Agency/Central Security Service > Article Commercial National Security Algorithm Suite 2.0” (CNSA 2.0) C…

LeetCode之最长回文子串

1.题目链接 5. 最长回文子串 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/longest-palindromic-substring/description/ 2.题目解析 对于这道题目我们可以使用动态规划的思路来求解&#xff0c;具体思路是&#xff0c;对于一个长度大于2的子串&…

新火种AI|微软和苹果放弃OpenAI董事会观察员席位

作者&#xff1a;一号 编辑&#xff1a;美美 微软苹果双双不做OpenAI“观察员”&#xff0c;OpenAI能更自由吗&#xff1f; 7月10消息&#xff0c;微软当地时间周一宣布将放弃在OpenAI董事会的观察员席位&#xff0c;他们称&#xff0c;OpenAI在过去八个月中取得了“重大进展…

2024机器遗忘(Machine Unlearning)技术分类-思维导图

1 介绍 机器遗忘&#xff08;Machine Unlearning&#xff09;是指从机器学习模型中安全地移除或"遗忘"特定的数据点或信息。这个概念源于数据隐私保护的需求&#xff0c;尤其是在欧盟通用数据保护条例&#xff08;GDPR&#xff09;等法规中提出的"被遗忘的权利…