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

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.大盗阿福题解

前言如果想看状态机的详解&#xff0c;点机这里:dp模型——状态机模型C详解1049. 大盗阿福阿福是一名经验丰富的大盗。趁着月黑风高&#xff0c;阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N家店铺&#xff0c;每家店中都有一些现金。阿福事先调查得知&#xff0c;只有当…...

python日志模块,loggin模块

python日志模块&#xff0c;loggin模块loggin模块日志的格式处理器种类日志格式的参数使用loggin模块 logging库采用模块化方法&#xff0c;并提供了几类组件&#xff1a;记录器&#xff0c;处理程序&#xff0c;过滤器和格式化程序。 记录器&#xff08;Logger&#xff09;&a…...

接口自动化入门-TestNg

目录1.TestNg介绍2、TestNG安装3、TestNG使用3.1 编写测试用例脚本3.2 创建TestNG.xml文件&#xff08;1&#xff09;创建testng.xml文件&#xff08;2&#xff09;修改testng.xml4、测试报告生成1.TestNg介绍 TestNg是Java中开源的自动化测试框架&#xff0c;灵感来源于Junit…...

Spring AOP —— 详解、实现原理、简单demo

目录 一、Spring AOP 是什么&#xff1f; 二、学习AOP 有什么作用&#xff1f; 三、AOP 的组成 3.1、切面&#xff08;Aspect&#xff09; 3.2、切点&#xff08;Pointcut&#xff09; 3.3、通知&#xff08;Advice&#xff09; 3.4、连接点 四、实现 Spring AOP 一个简…...

(蓝桥真题)异或数列(博弈)

题目链接&#xff1a;P8743 [蓝桥杯 2021 省 A] 异或数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入&#xff1a; 4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580 样例输出&#xff1a; 1 0 1 1 分析&#xff1a;容易想到对于异或最大值…...

4万字数字政府建设总体规划方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用。部分资料内容&#xff1a; 我省“数字政府”架构 &#xff08;一&#xff09; 总体架构。 “数字政府”总体架构包括管理架构、业务架构、技术架构。其中&#xff0c;管理架构体现“管运分离”的建设运营模式…...

CCF/CSP 201709-2公共钥匙盒100分

试题编号&#xff1a;201709-2试题名称&#xff1a;公共钥匙盒时间限制&#xff1a;1.0s内存限制&#xff1a;256.0MB问题描述&#xff1a;问题描述  有一个学校的老师共用N个教室&#xff0c;按照规定&#xff0c;所有的钥匙都必须放在公共钥匙盒里&#xff0c;老师不能带钥…...

【OC】Blocks模式

1. Block语法 Block语法完整形式如下&#xff1a; ^void (int event) {printf("buttonId:%d event%d\n", i, event); }完整形式的Block语法与一般的C语言函数定义相比&#xff0c;仅有两点不同。 没有函数名。带有“^”&#xff08;插入记号&#xff09;。 因为O…...

软件设计师教程(七)计算机系统知识-操作系统知识

软件设计师教程 软件设计师教程&#xff08;一&#xff09;计算机系统知识-计算机系统基础知识 软件设计师教程&#xff08;二&#xff09;计算机系统知识-计算机体系结构 软件设计师教程&#xff08;三&#xff09;计算机系统知识-计算机体系结构 软件设计师教程&#xff08;…...

蓝桥杯2023/3/2

1. 小蓝正在学习一门神奇的语言&#xff0c;这门语言中的单词都是由小写英文字母组 成&#xff0c;有些单词很长&#xff0c;远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词&#xff0c;他准备不再完全记忆这些单词&#xff0c;而是根据单词中哪个字母出现得最…...

【IoT】创业成功不可或缺的两个因素:能力和趋势

今天就来谈谈能力和趋势究竟哪个更重要的问题。 在谈成功的十大要素时&#xff0c;我曾经讲到&#xff1a; 一命、二运、三风水&#xff0c;这三个要素几乎不涉及任何个人的努力。 而趋势跟这三个要素又是息息相关的&#xff0c;这也类似雷军所说的飞猪理论。 只要风足够大&…...

2020蓝桥杯真题日期格式 C语言/C++

问题描述 小蓝要处理非常多的数据, 其中有一些数据是日期。 在小蓝处理的日期中有两种常用的形式: 英文形式和数字形式。 英文形式采用每个月的英文的前三个宁母作为月份标识, 后面跟两位数字 表示日期, 月份标识第一个字母大写, 后两个字母小写, 日期小于 10 时要补 前导 0s…...

总时差与自由时差

定义总时差&#xff08;总浮动时间&#xff09;&#xff08;TF&#xff0c;Total Free Time&#xff0c;不耽误项目总进度&#xff09;LS&#xff08;Latest Start&#xff09;-ES&#xff08;Earliest Start&#xff09;LF&#xff08;Latest Finish&#xff09;-EF&#xff0…...

LeetCode两个数组的交集-跳跃游戏- 最长有效括号

两个数组的交集 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出&#xff1a;[2] 示例 2&#xff1a; 输入&…...

mysql普通索引与唯一索引怎么选择

学习mysql普通索引与唯一索引选择记录总结&#xff0c;学习链接&#xff1a;http://gk.link/a/11YG8从mysql查询操作分析&#xff1a;普通索引&#xff1a;查到满足条件的第一条记录后&#xff0c;还会继续查找下一条记录&#xff0c;直到出现满足条件的记录出现后停止检索唯一…...

JavaWeb开发(三)3.5——Java的反射机制

一、反射机制的概念 指在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法&#xff0c;对于任意一个对象&#xff0c;都能调用它的任意一个方法。这种动态获取信息&#xff0c;及动态调用对象方法的功能叫java语言的反射机制。 Java反射机制的核心是在程序运行时动…...

Python每日一练(20230305)

目录 1. 正则表达式匹配 ★★★ 2. 寻找旋转排序数组中的最小值 II ★★★ 3. 删除排序链表中的重复元素 II ★★ 1. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个…...

SpringBoot三种方法实现定时发送邮件的案例

前言 小编我将用CSDN记录软件开发之路上所学的心得与知识&#xff0c;有兴趣的小伙伴可以关注一下&#xff01;也许一个人独行&#xff0c;可以走的很快&#xff0c;但是一群人结伴而行&#xff0c;才能走的更远&#xff01;让我们在成长的道路上互相学习&#xff0c;让我们共…...

opengl、opengl es、webgl介绍与opengl开发入门

1、OpenGL OpenGL&#xff08;英语&#xff1a;Open Graphics Library&#xff0c;译名&#xff1a;开放图形库或者“开放式图形库”&#xff09;常用于CAD、虚拟现实、科学可视化程序和电子游戏开发。OpenGL的高效实现&#xff08;利用了图形加速硬件&#xff09;存在于Windo…...

Vue3之组件间传值

何为组件间传值 在Vue3之组件文章中&#xff0c;我们学会了定义使用组件&#xff0c;但是我们似乎还缺少什么将组件之间联系起来&#xff0c;说到组件之间的联系就不得不提组件间的传值&#xff0c;而组件间的传值其实也不难理解&#xff0c;就是如何在子组件中接收到父组件传…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

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

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

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...