AcWing1049.大盗阿福题解
前言
如果想看状态机的详解,点机这里:dp模型——状态机模型C++详解
1049. 大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 T,表示一共有 T组数据。
接下来的每组数据,第一行是一个整数 N,表示一共有 N家店铺。
第二行是 N个被空格分开的正整数,表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据,输出一行。
该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50,
1≤N≤1e5
输入样例:
2
3
1 8 2
4
10 7 6 14输出样例:
8
24样例解释
对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。
对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。
这道题的大意就是,有t组数据,每个有n个超市,告诉你每一家的价钱,不能盗窃相邻的超市。
计算大盗能获得的最大利益。
解题思路
这道题有两种解法,第一种是普通的线性dp,第二种是状态机dp。
第一种
用f[i]表示前i家商店阿福可以获得的最大价值。
对于第i次选择,只能选偷或者不偷,偷就是f[i - 2] + w[i], 不偷就是f[i - 1]。
状态转移方程就是:
f[i] = max(f[i - 2] + w[i], f[i - 1]);完整ac代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int t, n;
int w[N], f[N];
int main() {scanf("%d", &t);while(t--) {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &w[i]);memset(f, -INF, sizeof f);f[0] = 0;for(int i = 1; i <= n; i++) f[i] = max(f[i - 2] + w[i], f[i - 1]);printf("%d\n", f[n]);}return 0;
}第二种就是今天讲到的状态机了,对于第i个超市,可以选择偷或者不偷,我们用1表示偷,0表示不偷(都是当前的超市)。

状态转移方程就是:
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];ac代码如下:
#include <bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d", &a);
const int N = 1e5 + 10, INF = 1e9;
int t, n;
int w[N], f[N][2];
int main() {read(t);while(t--) {read(n);for(int i = 1; i <= n; i++) read(w[i]);f[0][0] = 0, f[0][1] = -INF;for(int i = 1; i <= n; i++) {f[i][0] = max(f[i - 1][0], f[i - 1][1]);f[i][1] = f[i - 1][0] + w[i];}printf("%d\n", max(f[n][1], f[n][0]));}return 0;
}
相关文章:
AcWing1049.大盗阿福题解
前言如果想看状态机的详解,点机这里:dp模型——状态机模型C详解1049. 大盗阿福阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N家店铺,每家店中都有一些现金。阿福事先调查得知,只有当…...
python日志模块,loggin模块
python日志模块,loggin模块loggin模块日志的格式处理器种类日志格式的参数使用loggin模块 logging库采用模块化方法,并提供了几类组件:记录器,处理程序,过滤器和格式化程序。 记录器(Logger)&a…...
接口自动化入门-TestNg
目录1.TestNg介绍2、TestNG安装3、TestNG使用3.1 编写测试用例脚本3.2 创建TestNG.xml文件(1)创建testng.xml文件(2)修改testng.xml4、测试报告生成1.TestNg介绍 TestNg是Java中开源的自动化测试框架,灵感来源于Junit…...
Spring AOP —— 详解、实现原理、简单demo
目录 一、Spring AOP 是什么? 二、学习AOP 有什么作用? 三、AOP 的组成 3.1、切面(Aspect) 3.2、切点(Pointcut) 3.3、通知(Advice) 3.4、连接点 四、实现 Spring AOP 一个简…...
(蓝桥真题)异或数列(博弈)
题目链接:P8743 [蓝桥杯 2021 省 A] 异或数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入: 4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580 样例输出: 1 0 1 1 分析:容易想到对于异或最大值…...
4万字数字政府建设总体规划方案WORD
本资料来源公开网络,仅供个人学习,请勿商用。部分资料内容: 我省“数字政府”架构 (一) 总体架构。 “数字政府”总体架构包括管理架构、业务架构、技术架构。其中,管理架构体现“管运分离”的建设运营模式…...
CCF/CSP 201709-2公共钥匙盒100分
试题编号:201709-2试题名称:公共钥匙盒时间限制:1.0s内存限制:256.0MB问题描述:问题描述 有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥…...
【OC】Blocks模式
1. Block语法 Block语法完整形式如下: ^void (int event) {printf("buttonId:%d event%d\n", i, event); }完整形式的Block语法与一般的C语言函数定义相比,仅有两点不同。 没有函数名。带有“^”(插入记号)。 因为O…...
软件设计师教程(七)计算机系统知识-操作系统知识
软件设计师教程 软件设计师教程(一)计算机系统知识-计算机系统基础知识 软件设计师教程(二)计算机系统知识-计算机体系结构 软件设计师教程(三)计算机系统知识-计算机体系结构 软件设计师教程(…...
蓝桥杯2023/3/2
1. 小蓝正在学习一门神奇的语言,这门语言中的单词都是由小写英文字母组 成,有些单词很长,远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词,他准备不再完全记忆这些单词,而是根据单词中哪个字母出现得最…...
【IoT】创业成功不可或缺的两个因素:能力和趋势
今天就来谈谈能力和趋势究竟哪个更重要的问题。 在谈成功的十大要素时,我曾经讲到: 一命、二运、三风水,这三个要素几乎不涉及任何个人的努力。 而趋势跟这三个要素又是息息相关的,这也类似雷军所说的飞猪理论。 只要风足够大&…...
2020蓝桥杯真题日期格式 C语言/C++
问题描述 小蓝要处理非常多的数据, 其中有一些数据是日期。 在小蓝处理的日期中有两种常用的形式: 英文形式和数字形式。 英文形式采用每个月的英文的前三个宁母作为月份标识, 后面跟两位数字 表示日期, 月份标识第一个字母大写, 后两个字母小写, 日期小于 10 时要补 前导 0s…...
总时差与自由时差
定义总时差(总浮动时间)(TF,Total Free Time,不耽误项目总进度)LS(Latest Start)-ES(Earliest Start)LF(Latest Finish)-EF࿰…...
LeetCode两个数组的交集-跳跃游戏- 最长有效括号
两个数组的交集 给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1: 输入:nums1 [1,2,2,1], nums2 [2,2] 输出:[2] 示例 2: 输入&…...
mysql普通索引与唯一索引怎么选择
学习mysql普通索引与唯一索引选择记录总结,学习链接:http://gk.link/a/11YG8从mysql查询操作分析:普通索引:查到满足条件的第一条记录后,还会继续查找下一条记录,直到出现满足条件的记录出现后停止检索唯一…...
JavaWeb开发(三)3.5——Java的反射机制
一、反射机制的概念 指在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法,对于任意一个对象,都能调用它的任意一个方法。这种动态获取信息,及动态调用对象方法的功能叫java语言的反射机制。 Java反射机制的核心是在程序运行时动…...
Python每日一练(20230305)
目录 1. 正则表达式匹配 ★★★ 2. 寻找旋转排序数组中的最小值 II ★★★ 3. 删除排序链表中的重复元素 II ★★ 1. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个…...
SpringBoot三种方法实现定时发送邮件的案例
前言 小编我将用CSDN记录软件开发之路上所学的心得与知识,有兴趣的小伙伴可以关注一下!也许一个人独行,可以走的很快,但是一群人结伴而行,才能走的更远!让我们在成长的道路上互相学习,让我们共…...
opengl、opengl es、webgl介绍与opengl开发入门
1、OpenGL OpenGL(英语:Open Graphics Library,译名:开放图形库或者“开放式图形库”)常用于CAD、虚拟现实、科学可视化程序和电子游戏开发。OpenGL的高效实现(利用了图形加速硬件)存在于Windo…...
Vue3之组件间传值
何为组件间传值 在Vue3之组件文章中,我们学会了定义使用组件,但是我们似乎还缺少什么将组件之间联系起来,说到组件之间的联系就不得不提组件间的传值,而组件间的传值其实也不难理解,就是如何在子组件中接收到父组件传…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
表单设计器拖拽对象时添加属性
背景:因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...
【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项
一、条形码识别改名使用教程 打开软件并选择处理模式:打开软件后,根据要处理的文件类型,选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件,就选择 “PDF 识别模式”;若是处理图片文件&…...
RFID推动新能源汽车零部件生产系统管理应用案例
RFID推动新能源汽车零部件生产系统管理应用案例 一、项目背景 新能源汽车零部件场景 在新能源汽车零部件生产领域,电子冷却水泵等关键部件的装配溯源需求日益增长。传统 RFID 溯源方案采用 “网关 RFID 读写头” 模式,存在单点位单独头溯源、网关布线…...
前端异步编程全场景解读
前端异步编程是现代Web开发的核心,它解决了浏览器单线程执行带来的UI阻塞问题。以下从多个维度进行深度解析: 一、异步编程的核心概念 JavaScript的执行环境是单线程的,这意味着在同一时间只能执行一个任务。为了不阻塞主线程,J…...
