当前位置: 首页 > 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汽车电子、罗孚汽车、宾利汽车、福特汽车、捷…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...