【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 披萨大作战(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1067
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~
🍓OJ题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- 🥧 披萨大作战
- 题目描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
🥧 披萨大作战
题目描述
K小姐和A先生到披萨店点了一份圆形披萨,并嘱咐店员将披萨切成大小相同的偶数块。但是粗心的服务员把披萨切成了大小不一的 N N N 块,且 N N N 为奇数。
为了公平起见,两人商量了一个取披萨的规则:从K小姐开始,轮流取披萨。除了第一块披萨可以随意选取外,其余的披萨必须从上一个人取完的披萨的相邻位置开始取。
A先生每次都会选择剩下披萨中最大的一块,而K小姐知道A先生的这个特点。现在给定每块披萨的大小,请问K小姐最多能够取到多少大小的披萨呢?
输入格式
第一行包含一个正整数 N N N,表示披萨被切成了 N N N 块。
接下来 N N N 行,每行一个正整数,第 i i i 行的整数表示第 i i i 块披萨的大小 A i A_i Ai。
输出格式
输出一个整数,表示K小姐最多能够取到的披萨大小之和。
样例输入
5
8
2
10
5
7
样例输出
19
数据范围
- 3 ≤ N < 500 3 \le N < 500 3≤N<500,保证 N N N 为奇数
- 1 ≤ A i ≤ 2147483647 1 \le A_i \le 2147483647 1≤Ai≤2147483647
题解
本题可以使用记忆化搜索来解决。
定义 s o l v e ( L , R ) solve(L,R) solve(L,R) 表示当前还剩下第 L L L 块到第 R R R 块披萨时,K小姐能够取到的最大披萨大小之和。那么答案就是 m a x ( s o l v e ( ( i + 1 ) m o d N , ( i − 1 + N ) m o d N ) + A i ) max(solve((i+1) \bmod N, (i-1+N) \bmod N) + A_i) max(solve((i+1)modN,(i−1+N)modN)+Ai),其中 0 ≤ i < N 0 \le i < N 0≤i<N。
对于函数 s o l v e ( L , R ) solve(L,R) solve(L,R),我们可以分情况讨论:
-
如果 L = R L = R L=R,那么只剩下一块披萨,K小姐直接取走,因此 s o l v e ( L , R ) = A L solve(L,R) = A_L solve(L,R)=AL。
-
如果 L ≠ R L \neq R L=R,那么A先生会取走两端披萨中较大的一块。设 L ′ L' L′ 和 R ′ R' R′ 分别表示取走披萨后的左右端点,那么有:
- 如果 A L > A R A_L > A_R AL>AR,那么 L ′ = ( L + 1 ) m o d N , R ′ = R L' = (L+1) \bmod N, R' = R L′=(L+1)modN,R′=R
- 如果 A L ≤ A R A_L \le A_R AL≤AR,那么 L ′ = L , R ′ = ( R − 1 + N ) m o d N L' = L, R' = (R-1+N) \bmod N L′=L,R′=(R−1+N)modN
因此 s o l v e ( L , R ) = m a x ( A L + s o l v e ( L ′ , R ) , A R + s o l v e ( L , R ′ ) ) solve(L,R) = max(A_L + solve(L', R), A_R + solve(L, R')) solve(L,R)=max(AL+solve(L′,R),AR+solve(L,R′))。
为了避免重复计算,我们可以使用记忆化数组 d p dp dp 来保存已经计算过的状态。其中 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前还剩下第 i i i 块到第 j j j 块披萨时,K小姐能够取到的最大披萨大小之和。
时间复杂度 O ( N 2 ) O(N^2) O(N2),空间复杂度 O ( N 2 ) O(N^2) O(N2)。
参考代码
- Python
N = int(input())
A = [int(input()) for _ in range(N)]
dp = [[-1] * N for _ in range(N)]def solve(L, R):if A[L] > A[R]:L = (L + 1) % Nelse:R = (R - 1 + N) % Nif dp[L][R] != -1:return dp[L][R]if L == R:dp[L][R] = A[L]else:dp[L][R] = max(A[L] + solve((L+1)%N, R), A[R] + solve(L, (R-1+N)%N))return dp[L][R]ans = 0
for i in range(N):ans = max(ans, solve((i+1)%N, (i-1+N)%N) + A[i])print(ans)
- Java
import java.util.Scanner;public class Main {static int N;static int[] A;static int[][] dp;public static void main(String[] args) {Scanner sc = new Scanner(System.in);N = sc.nextInt();A = new int[N];for (int i = 0; i < N; i++) {A[i] = sc.nextInt();}dp = new int[N][N];for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {dp[i][j] = -1;}}int ans = 0;for (int i = 0; i < N; i++) {ans = Math.max(ans, solve((i+1)%N, (i-1+N)%N) + A[i]);}System.out.println(ans);}static int solve(int L, int R) {if (A[L] > A[R]) {L = (L + 1) % N;} else {R = (R - 1 + N) % N;}if (dp[L][R] != -1) {return dp[L][R];}if (L == R) {dp[L][R] = A[L];} else {dp[L][R] = Math.max(A[L] + solve((L+1)%N, R), A[R] + solve(L, (R-1+N)%N));}return dp[L][R];}
}
- Cpp
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 500;
int n, a[N], dp[N][N];int solve(int L, int R) {if (a[L] > a[R]) {L = (L + 1) % n;} else {R = (R - 1 + n) % n;}if (dp[L][R] != -1) {return dp[L][R];}if (L == R) {dp[L][R] = a[L];} else {dp[L][R] = max(a[L] + solve((L+1)%n, R), a[R] + solve(L, (R-1+n)%n));}return dp[L][R];
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}memset(dp, -1, sizeof(dp));int ans = 0;for (int i = 0; i < n; i++) {ans = max(ans, solve((i+1)%n, (i-1+n)%n) + a[i]);}cout << ans << endl;return 0;
}
相关文章:
【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 披萨大作战(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 …...
探索Facebook对世界各地文化的影响
随着数字化时代的到来,社交媒体已成为连接世界各地人们的重要平台之一。而在这个领域的巨头之一,Facebook不仅是人们沟通交流的场所,更是一座桥梁,将不同地域、文化的人们联系在一起。本文将探索Facebook对世界各地文化的影响&…...
导出requirements.txt
文章目录 requirements.txt导出环境中所有包导出当前项目的包可能遇到的问题 requirements.txt 在Python项目中,通常使用requirements.txt文件来列出所有需要的第三方库和模块。这个文件通常位于项目的根目录下,并且在安装Python项目时,可以…...
我主编的电子技术实验手册(09)——并联电路
本专栏是笔者主编教材(图0所示)的电子版,依托简易的元器件和仪表安排了30多个实验,主要面向经费不太充足的中高职院校。每个实验都安排了必不可少的【预习知识】,精心设计的【实验步骤】,全面丰富的【思考习…...
数据结构_二叉树
目录 一、树型结构 二、二叉树 2.1 概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储 2.5 遍历二叉树 2.6 操作二叉树 总结 一、树型结构 树是一种非线性的数据结构,它是由 n(n>0) 个有限结点组成一个具有层次关系的集合,一棵 n 个…...
Java线程池七个参数详解
ThreadPoolExecutor 是JDK中的线程池实现,这个类实现了一个线程池需要的各个方法,它提供了任务提交、线程管理、监控等方法 下面是 ThreadPoolExecutor 类的构造方法源码,其他创建线程池的方法最终都会导向这个构造方法,共有7个参…...
产品Web3D交互展示有什么优势?如何快速制作?
智能互联网时代,传统的图片、文字、视频等产品展示方式,因为缺少互动性,很难引起用户的兴趣,已经逐渐失去了宣传优势。 Web3D交互展示技术的出现,让众多品牌和企业找到了新的方向,线上产品展示不在枯燥无趣…...
Python | Leetcode Python题解之第171题Excel列表序号
题目: 题解: class Solution:def titleToNumber(self, columnTitle: str) -> int:number, multiple 0, 1for i in range(len(columnTitle) - 1, -1, -1):k ord(columnTitle[i]) - ord("A") 1number k * multiplemultiple * 26return n…...
【银河麒麟】高可用触发服务器异常重启,处理机制详解
1.服务器环境以及配置 【机型】物理机 处理器: Intel 内存: 126G 【内核版本】 4.19.90-25.16.v2101.ky10.x86_64 【银河麒麟操作系统镜像版本】 Kylin-Server-10-SP2-Release-Shenzhen-Metro-x86-Build01-20220619 Kylin-HA-10-SP2-Release-S…...
性能工具之 JMeter 常用组件介绍(七)
文章目录 一、后置处理器1、Regular Expression Extractor(正则表达式提取器)2、JSON Extractor(JSON表达式提取器)3、Regular Expression Extractor(正则表达式提取器) 二、小结 本文主要介绍JMeter主流后置处理器的功能 一、后置处理器 从上面可以看出后置处理可以插件挺多&a…...
Python学习笔记15:进阶篇(四)文件的读写。
文件操作 学习编程操作中,我觉得文件操作是必不可少的一部分。不管是读书的时候学习的c,c,工作的前学的java,现在学的Python,没学过的php和go,都有文件操作的模块以及库的支持,重要性毫无疑问。…...
角度调制与解调电路
music! (黄佳庆老师可爱捏) 调角 角度调制有较好的抗噪性能。 调相 相位变化的频率变化的微分,频率变化是相位变化的积分 相位的变化率就是频率 调频 调相与调频的关系 大F是输入信号的频率,大Ω是输入信号的角频率 …...
数据分析:微生物组差异丰度方法汇总
欢迎大家关注全网生信学习者系列: WX公zhong号:生信学习者Xiao hong书:生信学习者知hu:生信学习者CDSN:生信学习者2 介绍 微生物数据具有一下的特点,这使得在做差异分析的时候需要考虑到更多的问题&…...
Linux驱动开发(二)--字符设备驱动开发提升 LED驱动开发实验
1、地址映射 在编写驱动之前,需要知道MMU,也就是内存管理单元,在老版本的 Linux 中要求处理器必须有 MMU,但是现在Linux 内核已经支持无 MMU 的处理器了。 MMU的功能如下: 完成虚拟空间到物理空间的映射 内存保护&…...
钡铼BL101网关助力智慧城市路灯远程智能管控
在迈向智慧城市的征途中,基础设施的智能化改造是关键一环,而路灯作为城市脉络的照明灯塔,其智能化升级对于节能减排、提升城市管理效率具有重要意义。钡铼BL101网关,作为Modbus转MQTT的专业桥梁,正以其卓越的性能和广泛…...
如何优雅的使用Github Action服务来将Hexo部署到Github Pages
文章目录 参考文章前提条件1. 初始化Hexo2. 初始化仓库3. 创建Token4. 修改_config.yml5. 配置Github Action工作流6. 推送验证7. 配置Github Pages8. 修改Hexo主题样式10. 添加文章遇到了一些问题和方案1. 网站没有样式问题2. 图片不显示 参考文章 Bilibili视频教程-9分钟零成…...
After Effects 2024 mac/win版:创意视效,梦想起航
After Effects 2024是一款引领视效革命的专业软件,汇聚了创意与技术的精华。作为Adobe推出的全新版本,它以其强大的视频处理和动画创作能力,成为从事设计和视频特技的机构,如电视台、动画制作公司、个人后期制作工作室以及多媒体工…...
信息打点web篇----web后端源码专项收集
前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 专栏描述:因为第一遍过信息收集的时候,没怎么把收集做回事 导致后来在实战中,遭遇资产获取少,可渗透点少的痛苦,如今决定 从头来过,全面全方位…...
ArcGIS批量投影转换的妙用(地理坐标系转换为平面坐标系)
点击下方全系列课程学习 点击学习—>ArcGIS全系列实战视频教程——9个单一课程组合系列直播回放 这次文章我们来介绍一下,如何巧妙用要素数据集来实现要素的批量投影。不需要ArcGIS的模型构建器与解决。 例如,有多个要素要将CGCS_2000地理坐标系投…...
YOLOv10训练自己的数据集(图像目标检测)
目录 1、下载代码 2、环境配置 3、准备数据集 4、yolov10训练 可能会出现报错: 1、下载代码 源码地址:https://github.com/THU-MIG/yolov10 2、环境配置 打开源代码,在Terminal中,使用conda 创建虚拟环境配置 命令如下&a…...
解决不能拉取 docker 镜像
# 编辑镜像仓库文件 sudo vi /etc/docker/daemon.json { "registry-mirrors": ["https://registry.docker-cn.com","https://s3d6l2fh.mirror.aliyuncs.com"] }# 重启docker sudo systemctl restart docker参考 https://blog.csdn.net/u01019733…...
44、基于深度学习的癌症检测(matlab)
1、基于深度学习的癌症检测原理及流程 基于深度学习的癌症检测是利用深度学习算法对医学影像数据进行分析和诊断,以帮助医生准确地检测癌症病变。其原理和流程主要包括以下几个步骤: 数据采集:首先需要收集包括X光片、CT扫描、MRI等医学影像…...
Vue3 【仿 react 的 hook】封装 useTitle
效果预览 页码加载时,自动获取网页标题通过input输入框,可以实时改变网页标题 代码实现 index.vue <template><h1>网页的标题为: {{ titleRef }}</h1><p>通过input输入框实时改变网页的标题 <input v-model"…...
CSS 计数器
CSS 计数器 CSS 计数器是 CSS 中一个强大但经常被忽视的功能。它们允许开发者创建和管理计数器,这些计数器可以在文档中自动递增,非常适合用于编号章节、列表项或其他文档元素。在本文中,我们将深入探讨 CSS 计数器的使用方法、优势和实际应用场景。 CSS 计数器的基本概念…...
磁力搜索器,解读新一代的搜索引擎方式,磁力王、磁力猫等引擎的异同及原理
最近国内几年,不依赖追踪服务器的磁力搜索开始流行,成为新的资源搜索的方式。 我们平常所说的磁力王(jigecili.com)、磁力猫(yinghuacili.com)、bt磁力(btcili.cn)、磁力狗最新版(cilizhai.net)、磁力兔子、磁力宝、人…...
Apache Doris 全新分区策略 Auto Partition 应用场景与功能详解 | Deep Dive系列
编辑:SelectDB 技术团队 在当今数据驱动的时代,如何高效、有序地管理数据库中的海量数据成为挑战。为了处理庞大的数据集,分布式数据库引入了类似分区和分桶策略,通过将数据按特定规则划分成较小的单位并分布到不同节点上&#x…...
【Linux】关于在华为云中开放了端口后仍然无法访问的问题
已在安全组中添加规则: 通过指令: netstat -nltp | head -2 && netstat -nltp | grep 8080 运行结果: 可以看到服务器确实处于监听状态了. 通过指令 telnet 公网ip port 也提示: "正在连接xxx.xx.xx.xxx...无法打开到主机的连接。 在端口 8080: 连接失败"…...
Linux系统ubuntu20.04 无人机PX4 开发环境搭建(失败率很低)
Linux系统ubuntu20.04 无人机PX4 开发环境搭建 PX4固件下载开发环境搭建MAVROS安装安装地面站QGC PX4固件下载 PX4的源码处于GitHub,因为众所周知的原因git clone经常失败,此处从Gitee获取PX4源码和依赖模块。 git clone https://gitee.com/voima/PX4-…...
中间件(express)
中间件(express) 在Express.js中,中间件(Middleware)是一个重要的组成部分,用于处理HTTP请求和响应。中间件函数具有特定的签名,并可以接受请求对象(req)、响应对象&…...
【代码随想录算法训练Day44】LeetCode 322.零钱兑换、LeetCode 279.完全平方数、LeetCode139.单词拆分
Day44 动态规划第六天 LeetCode 322.零钱兑换 dp数组的含义:装满容量为j的背包需要的最少物品数为dp[j] 递推公式:dp[j]min(dp[j-coins[i]]1,dp[j]) 初始化:dp[0]0,dp[j]INT_MAX 遍历顺序:个数问题与遍历顺序无关,都…...
网站开发从什么学起/友链提交入口
1、 如何判断字段的值里面:那些数据包含小写字母或大小字母判断字段NAME的值里面有小写字母的记录方式1:方式2判断字段NAME的值里面有大写字母的记录方式1:方式2:2、如何判断字段里面的值里面包含特殊字符例如,我想找出表TEST的字…...
二维码在线制作免费/谷歌seo站内优化
时间:2016年11月09日星期三说明:Linux系统上安装JDK,系统为centOS7 64位步骤一:上传JDK安装包到Linux服务器使用FileZilla工具将jdk的linux安装包上传到服务器任意目录步骤二:使用SecureCRT工具连接Linux服务器使用Sec…...
域名备案 没有网站/武汉seo招聘信息
编号:0737 座位号 2018~2019学年度第二学期期末考试 烹饪原料学(2)试题 2019年4月 一、名词解释(本大题共4小题,每题5分,共20分)。 高温贮藏法 辅助原料 色拉油 香辛料 二、单…...
wordpress 清除/抖音指数
定义:定义一系列算法,将它们一个个封装起来,并且使他们之间可以相互替换。本模式使得算法可以独立于使用它的客户而变化。 类型:对象行为型模式 类图: 策略模式是对算法的封装,把一系列的算法分别封装到对应…...
专业做公司logo的网站/今天今日头条新闻
1、问题概述 我的OS是Windows8.1 64位,尝试安装github desktop,始终安装失败:进度到50%左右就炸了。提示说:网络出错。(我100M电信,网络出错?我一直都在上网好吗)。 谷歌搜索了解决方…...
香港公司注册处官方网站/太原网站推广公司
有人的地方,就有江湖。人往往是最难揣摩的。如果有一面神奇的魔镜能看出一个人的内心,世界会不会变得更加美好呢?Linux 的世界里,file 就是这样一面魔镜,它可以看到每个文件的内心。file 命令可以识别出文件的类型和编…...