1301:大盗阿福

经典的dp打家劫舍问题
状态设计
dp[i][0]:在前i个店铺中选,且不选第i家的最大和
dp[i][1]:在前i个店铺中选,且选第i家的最大和
状态转移
dp[i][0] = max(dp[i-1][1], dp[i-1][0];
第i家店不选,那么我们可以选第i-1个店 也可以不选(第i-1个店)
dp[i][1] = dp[i-1][0] + a[i];
第i家店选,那么我们第i-1个店一定不能选(因为不能选相邻两个),还要记得加上第i家店的价值
初始化
dp[1][0] = 0
dp[1][1] = a[1]
(不懂得化可以再看一下 ⌈状态设计⌋ )
答案
max(dp[n][0], dp[n][1])
代码
//大盗阿福
#include <iostream>
#include <cstring>using namespace std;const int N = 100010;
int a[N], dp[N][1];int main() {int t;scanf ("%d", &t);while (t --) {/*状态设计dp[i][0/1] : 打劫前i个店铺可得的最大金额, 且不包含/包含第i个数字的最大值状态转移dp[i][0] = max(dp[i-1][1], dp[i-1][0]);dp[i][1] = dp[i-1][0] + a[i];初始化dp[1][1] = a[1];输出max(dp[n][0], dp[n][1]);*/int n;scanf ("%d", &n);for (int i = 1; i <= n; i ++)scanf ("%d", &a[i]);dp[1][1] = a[1];for (int i = 2; i <= n; i ++)dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]), dp[i][1] = dp[i - 1][0] + a[i];printf ("%d\n", max(dp[n][0], dp[n][1]));}return 0;
}
/*
【输入样例】
2
3
1 8 2
4
10 7 6 14
【输出样例】
8
24
*/原题链接:
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
相关文章:
1301:大盗阿福
经典的dp打家劫舍问题状态设计dp[i][0]:在前i个店铺中选,且不选第i家的最大和dp[i][1]:在前i个店铺中选,且选第i家的最大和状态转移dp[i][0] max(dp[i-1][1], dp[i-1][0];第i家店不选,那么我们可以选第i-1个店 也可以…...
Netty——序列化的作用及自定义协议
序列化的作用及自定义协议序列化的重要性大小对比效率对比自定义协议序列化数据结构自定义编码器自定义解码器安全性验证NettyClientNettyServerNettyClientTestHandlerNettyServerTestHandler结果上一章已经说了怎么解决沾包和拆包的问题,但是这样离一个成熟的通信…...
一起Talk Android吧(第五百零五回:如何调整组件在约束布局中的大小)
文章目录 背景介绍调整方法各位看官们大家好,上一回中咱们说的例子是"如何调整组件在约束布局中的位置",这一回中咱们说的例子是" 如何调整组件在约束布局中的大小"。闲话休提,言归正转, 让我们一起Talk Android吧! 背景介绍 在使用约束(constraintl…...
【数据库】数据库的完整性
第五章 数据库完整性 数据库完整性 数据库的完整性是指数据的正确性和相容性 数据的正确性是指数据是符合现实世界语义,反映当前实际状况的数据的相容性是指数据库的同一对象在不同的关系中的数据是符合逻辑的 关系模型中有三类完整性约束:实体完整性…...
基因净化车间装修设计方案SICOLAB
基因净化车间的设计方案应该根据实际需求进行定制,以下是一些规划建设要点和洁净设计要注意的事项:一、净化车间规划建设要点:(1)基因车间的面积应该根据实验项目的规模进行规划,包括充足的操作区域和足够的…...
java 内部类的四种“写法”
基本介绍语法格式分类成员内部类静态内部类局部内部类匿名内部类(🐂🖊)一、基本介绍 : 1.概述当一个类的内部又完整地嵌套了另一个类时,被嵌套于内部的“内核”我们称之为“内部类”(inner class);而包含该…...
【python】main方法教程
嗨害大家好鸭! 我是小熊猫~ 首先 if name "main": 可以看成是python程序的入口, 就像java中的main()方法, 但不完全正确。 事实上python程序是从上而下逐行运行的, 在.py文件中, 除…...
公司对不同职级能力抽象要求的具体化
要先把当前级别要求的能力提升到精通,然后尝试做下一级别的事情。 但可能不确定高一级的能力要求究竟怎样,不同Title,如“工程师”“高级工程师”和“资深工程师”等。但这样 Title 对我们理解不同级别的能力要求,完全无用。“高…...
Java之MinIO存储桶和对象API使用
环境搭建 创建一个 maven项目,引入依赖: <!-- minio依赖--><dependency><groupId>io.minio</groupId><artifactId>minio</artifactId><version>8.3.3</version></dependency><!-- 官方 minio…...
如何用java实现同时进行多个请求,可以将它们并行执行,从而减少总共的请求时间。
1.使用线程池 通过使用Java提供的线程池,可以将多个请求分配到不同的线程中并行执行。可以通过创建固定数量的线程池,然后将请求分配给线程池来实现。线程池会自动管理线程的数量和复用,从而减少了线程创建和销毁的开销,提高了程序…...
高端装备的AC主轴头结构
加工机器人的AC主轴头和位置相关动力学特性1. 位置依赖动态特性及其复杂性2. AC主轴头2.1 常见主轴头摆角结构2.2 摆动机构3. 加装AC主轴头的作用和局限性4. 切削机器人的减速器类型5. 其他并联结构形式参考文献资料1. 位置依赖动态特性及其复杂性 However, FRF measurements …...
【Proteus仿真】【51单片机】粮仓温湿度控制系统设计
文章目录一、功能简介二、软件设计三、实验现象联系作者一、功能简介 本项目使用Proteus8仿真51单片机控制器,使用声光报警模块、LCD1602显示模块、DHT11温湿度模块、继电器模块、加热加湿除湿风扇等。 主要功能: 系统运行后,LCD1602显示传…...
【LINUX】环境变量以及main函数的参数
文章目录前言环境变量常见环境变量:设置环境变量:和环境变量相关的命令:环境变量的组织方式:获取环境变量环境变量可以被子进程继承环境变量总结main函数的参数前言 大家好久不见,今天分享的内容是环境变量和main函数…...
使用Pyparsing为嵌入式开发定义自己的脚本语言
Python在嵌入式开发中也很流行生成实用脚本。Pyparsing还允许你轻松地定义在Python上下文中运行的定制脚本语言。Python实现的系统旨在能够独立执行用户传递的一系列命令。你希望系统以脚本的形式接收命令。用户应该能够定义条件。这种对通信中逻辑元素的最初简单的声音要求&am…...
C win32基础学习(二)
上一篇我们已经介绍了关于窗口程序的一些基本知识。从本篇开始我们将正式进入C win32的学习中去。 正文 窗口创建过程 定义WinMain函数 定义窗口处理函数(自定义,处理消息) 注册窗口类(向操作系统写入一些数据) 创建窗口(内存…...
理论五:控制反转、依赖反转、依赖注入,这三者有何区别和联系?
关于SOLID原则,我们已经学过单一职责、开闭、里式替换、接口隔离这四个原则。今天,我们再来学习最后一个原则:依赖反转原则。在前面几节课中,我们讲到,单一职责原则和开闭原则的原理比较简单,但是,想要在实践中用好却比较难。而今天我们要讲到的依赖反转原则正好相反。这个原则…...
读书笔记//《数据分析之道》
出版时间:2022年 作者曾在互联网大厂做数据分析。从举例可以洞见作者的工作经历。 点评:作者在数据分析领域非常资深,尝试在书中提供一个数据分析工作框架参考。书本内容有点感觉是ppt的集合,辅以案例说明。不过,干货还…...
1个串口用1根线实现多机半双工通信+开机控制电路
功能需求: 主机使用一个串口,与两个从机进行双向通信,主机向从机发送数据,从机能够返回数据,由于结构限制,主机与从机之间只有3根线(电源、地、数据线),并且从机上没有设…...
KUKA机器人外部自动运行模式的相关信号配置
KUKA机器人外部自动运行模式的相关信号配置 通过例如PLC这样的控制器来进行外部自动运行控制时,运行接口向机器人控制系统发出机器人进程的相关信号(例如运行许可、故障确认、程序启动等),机器人向上级控制系统发送有关运行状态和故障状态的信息。 必需的配置: 配置CEL…...
【RabbitMQ笔记02】消息队列RabbitMQ七种模式之最简单的模式
这篇文章,主要介绍RabbitMQ消息队列中七种模式里面最简单的使用模式。 目录 一、消息队列的使用 1.1、消息队列七种模式 1.2、最简单的模式使用 (1)引入依赖 (2)编写生产者 (3)编写消费者…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
