当前位置: 首页 > news >正文

蓝桥杯算法心得——想吃冰淇淋和蛋糕(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)

大家好&#xff0c;我是晴天学长&#xff0c;dp题&#xff0c;怎么设计状态很重要&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .想吃冰淇淋和蛋糕 想吃冰淇淋与蛋糕 输入格式 第一行输入一个整数n。…...

LLM之RAG实战(二):使用LlamaIndex + Metaphor实现知识工作自动化

最先进的大型语言模型&#xff08;LLM&#xff09;&#xff0c;如ChatGPT、GPT-4、Claude 2&#xff0c;具有令人难以置信的推理能力&#xff0c;可以解锁各种用例——从洞察力提取到问答&#xff0c;再到通用工作流自动化。然而&#xff0c;他们检索上下文相关信息的能力有限。…...

【容器】Docker打包Linux操作系统迁移

0x0 场景 因老服务器操作系统文centos6.5&#xff0c;现要迁移至uos v20 1050a&#xff08;底层centos8&#xff09;&#xff0c;其中需要迁移的应用组件有&#xff1a; mysql 、tomcat、apachehttpd&#xff0c;因版本跨越太大&#xff0c;导致centos8直接安装无法完全恢复原…...

redis基本数据结构

Redis入门&#xff1a;五大数据类型 文章目录 Redis入门&#xff1a;五大数据类型一.概述二.Redis的基本了解三.Redis五大数据类型1.String (字符串)2.List(列表)3.Set集合(元素唯一不重复)4.Hash集合5.zSet(有序集合) 一.概述 什么是Redis Redis&#xff08;Remote Dictiona…...

Learning Normal Dynamics in Videos with Meta Prototype Network 论文阅读

文章信息&#xff1a;发表在cvpr2021 原文链接&#xff1a; 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分答案)

基于最近大家都在考这个应用开发者基础认证考试&#xff0c;因此出了一期&#xff0c;一样复制word里面搜索做&#xff0c;很快&#xff0c;当然good luck 判断题 Ability是系统调度应用的最小单元,是能够完成一个独立功能的组件。一个应用可以包含一个或多个Ability。 正确(Tr…...

Ubuntu20.04 Kimera Semantic运行记录

Ubuntu20.04 Kimera Semantic 官方bag运行记录 以下基本为官方教程&#xff0c;有部分修改 依赖 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系统故障包括硬盘故障、控制器故障、电源故障、写入错误和热插拔错误。下面结合这些故障的应用场景和常规维修处理流程来详细讨论&#xff1a; 硬盘故障&#xff1a; 应用场景&#xff1a;在服务器RAID系统中&#xff0c;硬盘故障是最常见的问题之一。硬盘可能…...

计算机网络——数据链路层-封装成帧(帧定界、透明传输-字节填充,比特填充、MTU)

目录 介绍 帧定界 PPP帧 以太网帧 透明传输 字节填充&#xff08;字符填充&#xff09; 比特填充 比特填充习题 MTU 介绍 所谓封装成帧&#xff0c;就是指数据链路层给上层交付下来的协议数据单元添加帧头和帧尾&#xff0c;使之成为帧。 例如下图所示&#xff1a; …...

MySQL笔记-第03章_基本的SELECT语句

视频链接&#xff1a;【MySQL数据库入门到大牛&#xff0c;mysql安装到优化&#xff0c;百科全书级&#xff0c;全网天花板】 文章目录 第03章_基本的SELECT语句1. SQL概述1.1 SQL背景知识1.2 SQL语言排行榜1.3 SQL 分类 2. SQL语言的规则与规范2.1 基本规则2.2 SQL大小写规范 …...

FTP服务文件上传失败,错误码553的排故过程

本文主要记录文件上传失败&#xff0c;错误码553的排故过程。 1 背景 树莓派通过FTP给嵌入式板卡传输文件&#xff0c;好几套设备&#xff0c;发现有的能传输成功&#xff0c;有的传输不成功。树莓派和嵌入式板卡都一样的&#xff0c;出现问题时感觉很懵。 2 逐项对比 2.1 自…...

音频录制软件哪个好?帮助你找到最合适的一款

音频录制软件是日常工作、学习和创作中不可或缺的一部分。选择一个适合自己需求的录音软件对于确保音频质量和提高工作效率至关重要。可是您知道音频录制软件哪个好吗&#xff1f;本文将深入探讨两种常见的音频录制软件&#xff0c;通过详细的步骤指南&#xff0c;帮助您了解它…...

9.Unity搭建HTTP服务器

搭建HTTP服务器的几种方式 //1.使用别人做好的HTTP服务器软件&#xff0c;一般作为资源服务器时使用该方式&#xff08;学习阶段建议使用&#xff09; //2.自己编写HTTP服务器应用程序&#xff0c;一般作为Web服务器 或者 短链接游戏服务器时 使用该方式 使用别人做好的HTTP服…...

C# 热键注册工具类

写在前面 介绍一个验证过的热键注册工具类&#xff0c;使用系统类库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技术可行性&#xff1a;…...

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…...

软件工程 室友整理

如何理解结构化需求分析方法的基本思想; 结构化分析方法是一种面向数据流的需求分析方法&#xff0c;其中数据作为独立实体转换&#xff0c;数据建模定义数据的属性和关系&#xff0c;操作数据的处理建模表名当做数据在系统流动时候处理如何转换数据 简述面向对象的基本概念&a…...

JVM==>图解字节码指令

一&#xff0c;原始代码 我们来看一下执行这段代码的具体流程 那执行这段代码中 JVM就会把已经编译好的.class文件加载到内存中&#xff0c;交给CPU运行 1&#xff09;常量池载入运行时常量池 我们发现 10 并没有被存入常量池中&#xff0c; 这是因为short范围以内的数字不会…...

MISRA C 2012 标准浅析

MISRA(The Motor Industry Software Reliability Association)&#xff0c;汽车工业软件可靠性联会&#xff1b; 1994年&#xff0c;英国成立。致力于协助汽车厂商开发安全可靠的软件的跨国协会&#xff0c;其成员包括&#xff1a;AB汽车电子、罗孚汽车、宾利汽车、福特汽车、捷…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...

渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用

阻止除自定义标签之外的所有标签 先输入一些标签测试&#xff0c;说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时&#xff08;如通过点击或键盘导航&…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

react-pdf(pdfjs-dist)如何兼容老浏览器(chrome 49)

之前都是使用react-pdf来渲染pdf文件&#xff0c;这次有个需求是要兼容xp环境&#xff0c;xp上chrome最高支持到49&#xff0c;虽然说iframe或者embed都可以实现预览pdf&#xff0c;但为了后续的定制化需求&#xff0c;还是需要使用js库来渲染。 chrome 49测试环境 能用的测试…...

初级程序员入门指南

初级程序员入门指南 在数字化浪潮中&#xff0c;编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言&#xff0c;明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 &#xff08;一&#xff09;编程语言抉择 编…...

[C++错误经验]case语句跳过变量初始化

标题&#xff1a;[C错误经验]case语句跳过变量初始化 水墨不写bug 文章目录 一、错误信息复现二、错误分析三、解决方法 一、错误信息复现 write.cc:80:14: error: jump to case label80 | case 2:| ^ write.cc:76:20: note: crosses initialization…...