蓝桥杯算法心得——想吃冰淇淋和蛋糕(dp)
大家好,我是晴天学长,dp题,怎么设计状态很重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪
1) .想吃冰淇淋和蛋糕

想吃冰淇淋与蛋糕
输入格式
第一行输入一个整数n。代表天数。
第二行输入一个序列a,代表吃蛋糕每天提供的快乐值。
第三行输入一个序列b,代表吃冰淇淋每天提供的快乐值。
输出格式
输出获得的快乐值总和最大的值。
样例输入
3
3 4 4
2 2 1
样例输出
10
说明 你可以第一天吃冰淇淋, 第二天吃蛋糕,第三天吃蛋糕,最终是2+4+4=10. 你不能选择3, 4,4,因为无法连续天玩同一款游戏。
评测数据规模
1≤n≤10,1≤ai,bi< 10*.
2) .算法思路
想吃冰淇淋与蛋糕
1.有4个状态。
(1)连续吃蛋糕一天
(2)连续吃蛋糕两天
(3)连续吃冰淇淋一天
(4)连续吃冰淇淋两天
2.建立一个二维的dp数组
3.遍历n。
3).算法步骤
1.读取输入的数据,包括蛋糕和冰淇淋的数量以及它们的价值。
2.创建一个二维数组dp,用于存储中间结果。dp[i][j]表示在第i个位置选择了蛋糕或冰淇淋后,所能获得的最大价值。
3.初始化dp数组的第一行。根据题目要求,第一个位置可以选择蛋糕或冰淇淋,因此将其价值赋给dp[0][0]和dp[0][1],同时将冰淇淋的价值赋给dp[0][2]和dp[0][3]。
4.从第二行开始,遍历每个位置和选择。对于第i个位置和第j个选择,根据题目给出的规则,更新dp[i][j]的值。
(1)如果j等于0,表示选择了蛋糕,并且前一个位置选择了冰淇淋,所以dp[i][j]等于前一个位置选择冰淇淋的最大价值加上当前蛋糕的价值。
如果j等于1,表示选择了蛋糕,并且前一个位置也选择了蛋糕,所以dp[i][j](2)等于前一个位置选择蛋糕的最大价值加上当前蛋糕的价值。
如果j等于2,表示选择了冰淇淋,并且前一个位置选择了蛋糕,所以dp[i][j](3)等于前一个位置选择蛋糕的最大价值加上当前冰淇淋的价值。
(4)如果j等于3,表示选择了冰淇淋,并且前一个位置也选择了冰淇淋,所以dp[i][j]等于前一个位置选择冰淇淋的最大价值加上当前冰淇淋的价值。
5.遍历完所有位置和选择后,找到dp数组最后一行的最大值,即为所求的最大价值。
6.输出最大价值。
4). 代码实例
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(System.out);static String[] lines;public static void main(String[] args) throws IOException {lines = in.readLine().split(" ");int n = Integer.parseInt(lines[0]);int[] dangao = new int[n];int[] bingqiling = new int[n];lines = in.readLine().split(" ");for (int i = 0; i < n; i++) {dangao[i] = Integer.parseInt(lines[i]);}lines = in.readLine().split(" ");for (int i = 0; i < n; i++) {bingqiling[i] = Integer.parseInt(lines[i]);}int[][] dp = new int[n][4];dp[0][0] = dangao[0];dp[0][1] = dangao[0];dp[0][2] = bingqiling[0];dp[0][3] = bingqiling[0];for (int i = 1; i < n; i++) {for (int j = 0; j < 4; j++) {if (j == 0) {dp[i][j] = Math.max(dp[i - 1][2], dp[i - 1][3]) + dangao[i];}if (j == 1) {dp[i][j] = dp[i - 1][0] + dangao[i];}if (j == 2) {dp[i][j] = Math.max(dp[i - 1][0], dp[i - 1][1]) + bingqiling[i];}if (j == 3) {dp[i][j] = dp[i - 1][2] + bingqiling[i];}}}long max = Integer.MIN_VALUE;for (int i = 0; i < 4; i++) {max = Math.max(max, dp[n - 1][i]);}out.println(max);out.flush();out.close();}
}
4).总结
- 状态的定义。
试题链接:
相关文章:
蓝桥杯算法心得——想吃冰淇淋和蛋糕(dp)
大家好,我是晴天学长,dp题,怎么设计状态很重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪 1) .想吃冰淇淋和蛋糕 想吃冰淇淋与蛋糕 输入格式 第一行输入一个整数n。…...
LLM之RAG实战(二):使用LlamaIndex + Metaphor实现知识工作自动化
最先进的大型语言模型(LLM),如ChatGPT、GPT-4、Claude 2,具有令人难以置信的推理能力,可以解锁各种用例——从洞察力提取到问答,再到通用工作流自动化。然而,他们检索上下文相关信息的能力有限。…...
【容器】Docker打包Linux操作系统迁移
0x0 场景 因老服务器操作系统文centos6.5,现要迁移至uos v20 1050a(底层centos8),其中需要迁移的应用组件有: mysql 、tomcat、apachehttpd,因版本跨越太大,导致centos8直接安装无法完全恢复原…...
redis基本数据结构
Redis入门:五大数据类型 文章目录 Redis入门:五大数据类型一.概述二.Redis的基本了解三.Redis五大数据类型1.String (字符串)2.List(列表)3.Set集合(元素唯一不重复)4.Hash集合5.zSet(有序集合) 一.概述 什么是Redis Redis(Remote Dictiona…...
Learning Normal Dynamics in Videos with Meta Prototype Network 论文阅读
文章信息:发表在cvpr2021 原文链接: Learning Normal Dynamics in Videos with Meta Prototype Network 摘要1.介绍2.相关工作3.方法3.1. Dynamic Prototype Unit3.2. 视频异常检测的目标函数3.3. 少样本视频异常检测中的元学习 4.实验5.总结代码复现&a…...
Unity 关于SpriteRenderer 和正交相机缩放
float oldWidth 750f;float oldHeight 1334f;float newWidth Screen.width;float newHeight Screen.height;float oldAspect oldWidth / oldHeight;float newAspect newWidth / newHeight;//水平方向缩放float horizontalCompressionRatio newAspect / oldAspect;//垂直…...
HarmonyOS应用开发者基础认证考试(98分答案)
基于最近大家都在考这个应用开发者基础认证考试,因此出了一期,一样复制word里面搜索做,很快,当然good luck 判断题 Ability是系统调度应用的最小单元,是能够完成一个独立功能的组件。一个应用可以包含一个或多个Ability。 正确(Tr…...
Ubuntu20.04 Kimera Semantic运行记录
Ubuntu20.04 Kimera Semantic 官方bag运行记录 以下基本为官方教程,有部分修改 依赖 sudo apt-get install python3-wstool python3-catkin-tools protobuf-compiler autoconf sudo apt-get install ros-noetic-cmake-modulessudo apt-get install ros-noetic-i…...
服务器RAID系统的常见故障,结合应用场景谈谈常规的维修处理流程
常见的服务器RAID系统故障包括硬盘故障、控制器故障、电源故障、写入错误和热插拔错误。下面结合这些故障的应用场景和常规维修处理流程来详细讨论: 硬盘故障: 应用场景:在服务器RAID系统中,硬盘故障是最常见的问题之一。硬盘可能…...
计算机网络——数据链路层-封装成帧(帧定界、透明传输-字节填充,比特填充、MTU)
目录 介绍 帧定界 PPP帧 以太网帧 透明传输 字节填充(字符填充) 比特填充 比特填充习题 MTU 介绍 所谓封装成帧,就是指数据链路层给上层交付下来的协议数据单元添加帧头和帧尾,使之成为帧。 例如下图所示: …...
MySQL笔记-第03章_基本的SELECT语句
视频链接:【MySQL数据库入门到大牛,mysql安装到优化,百科全书级,全网天花板】 文章目录 第03章_基本的SELECT语句1. SQL概述1.1 SQL背景知识1.2 SQL语言排行榜1.3 SQL 分类 2. SQL语言的规则与规范2.1 基本规则2.2 SQL大小写规范 …...
FTP服务文件上传失败,错误码553的排故过程
本文主要记录文件上传失败,错误码553的排故过程。 1 背景 树莓派通过FTP给嵌入式板卡传输文件,好几套设备,发现有的能传输成功,有的传输不成功。树莓派和嵌入式板卡都一样的,出现问题时感觉很懵。 2 逐项对比 2.1 自…...
音频录制软件哪个好?帮助你找到最合适的一款
音频录制软件是日常工作、学习和创作中不可或缺的一部分。选择一个适合自己需求的录音软件对于确保音频质量和提高工作效率至关重要。可是您知道音频录制软件哪个好吗?本文将深入探讨两种常见的音频录制软件,通过详细的步骤指南,帮助您了解它…...
9.Unity搭建HTTP服务器
搭建HTTP服务器的几种方式 //1.使用别人做好的HTTP服务器软件,一般作为资源服务器时使用该方式(学习阶段建议使用) //2.自己编写HTTP服务器应用程序,一般作为Web服务器 或者 短链接游戏服务器时 使用该方式 使用别人做好的HTTP服…...
C# 热键注册工具类
写在前面 介绍一个验证过的热键注册工具类,使用系统类库user32.dll中的RegisterHotkey函数来实现全局热键的注册。 代码实现 [Flags]public enum KeyModifiers{Alt 1,Control 2,Shift 4,Windows 8,NoRepeat 0x4000}public static class HotKeyHelper{[DllImp…...
nodejs微信小程序+python+PHP天天网站书城管理系统的设计与实现-计算机毕业设计推荐
目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性:…...
Hive环境准备[重点学习]
1.前提启动hadoop集群 hadoop在统一虚拟机中已经配置了环境变量 启动hdfs和yarn集群 命令:start-all.sh [rootnode1 /]# start-all.sh启动mr历史服务 命令:mapred --daemon start historyserver [rootnode1 /]# mapred --daemon start historyserver检查服务 命令:jps [r…...
软件工程 室友整理
如何理解结构化需求分析方法的基本思想; 结构化分析方法是一种面向数据流的需求分析方法,其中数据作为独立实体转换,数据建模定义数据的属性和关系,操作数据的处理建模表名当做数据在系统流动时候处理如何转换数据 简述面向对象的基本概念&a…...
JVM==>图解字节码指令
一,原始代码 我们来看一下执行这段代码的具体流程 那执行这段代码中 JVM就会把已经编译好的.class文件加载到内存中,交给CPU运行 1)常量池载入运行时常量池 我们发现 10 并没有被存入常量池中, 这是因为short范围以内的数字不会…...
MISRA C 2012 标准浅析
MISRA(The Motor Industry Software Reliability Association),汽车工业软件可靠性联会; 1994年,英国成立。致力于协助汽车厂商开发安全可靠的软件的跨国协会,其成员包括:AB汽车电子、罗孚汽车、宾利汽车、福特汽车、捷…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
电脑桌面太单调,用Python写一个桌面小宠物应用。
下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡,可以响应鼠标点击,并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...
