蓝桥杯算法心得——想吃冰淇淋和蛋糕(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汽车电子、罗孚汽车、宾利汽车、福特汽车、捷…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...
