DP(状态机模型)
大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 T,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据,输出一行。
该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50
1≤N≤10^5
输入样例:
2
3
1 8 2
4
10 7 6 14
输出样例:
8
24
样例解释
对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。
对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。
线性DP
#include<iostream>
using namespace std;
const int N=1e5+10;
int f[N];
int w[N];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&w[i]);for(int i=1;i<=n;i++){f[i]=max(f[i-1],f[i-2]+w[i]);}cout<<f[n]<<endl;}return 0;
}
状态机的写法
#include<iostream>
using namespace std;
const int N=1e5+10,INF=1e9;
int f[N][2];
int w[N];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&w[i]);f[0][0]=0,f[0][1]=-INF;//f[0][1]=0也可 f[0][0]与f[0][1]相当于入口 入口肯定接到f[1][0]上肯定接到0 上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][0],f[n][1]));}return 0;}
股票买卖 IV
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。
输入格式
第一行包含整数 N 和 k,表示数组的长度以及你可以完成的最大交易笔数。
第二行包含 N 个不超过 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
1≤N≤10^5
1≤k≤100
输入样例1:
3 2
2 4 1
输出样例1:
2
输入样例2:
6 2
3 2 6 5 0 3
输出样例2:
7
样例解释
样例1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
样例2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.
股票买卖 V
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
输入格式
第一行包含整数 N,表示数组长度。
第二行包含 N 个不超过 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
1≤N≤10^5
输入样例:
5
1 2 3 0 2
输出样例:
3
样例解释
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。
设计密码
你现在需要设计一个密码 S,S 需要满足:
- S 的长度是 N;
- S 只包含小写英文字母;
- S 不包含子串 T;
例如:abcabc 和 abcdeabcde 是 abcdeabcde 的子串,abdabd 不是 abcdeabcde 的子串。
请问共有多少种不同的密码满足要求?
由于答案会非常大,请输出答案模 10^9+7 的余数。
输入格式
第一行输入整数N,表示密码的长度。
第二行输入字符串T,T中只包含小写字母。
输出格式
输出一个正整数,表示总方案数模 10^9+7 后的结果。
数据范围
1≤N≤50
1≤|T|≤N,|T|是T的长度。
输入样例1:
2
a
输出样例1:
625
输入样例2:
4
cbc
输出样例2:
456924
相关文章:
DP(状态机模型)
大盗阿福 阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺,每家店中都有一些现金。 阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动&#x…...
按照指定的文件顺序进行scp传输
前言 scp 默认传输顺序是按照文件名进行排序的, 但我当前工作中遇到要验证两台机器的神经网络层的精度,需要把网络层的输入输出(假设有100层, 一共64G) 从机器1传输到机器2 , 然后进行对比;这种情况下最好…...
小红书数据分析丨现实版模拟人生,这届网友热衷于“云开店”?
近期,小红书出现的一个神秘的热心群体,他们经常活跃在各种小店店主发布的求助帖评论区中,积极地帮助店主出谋划策,寻找小店经营的优化之道,成功帮助小店成功转亏为盈!江湖人称一一云股东。小红书话题#爱上帮…...
休闲卤味强势崛起:卤味零食成为新一代热门美食
随着人们生活水平的提高和消费观念的转变,休闲卤味逐渐成为了人们日常生活中的热门美食。据最新数据显示,2022年,我国卤味市场销售额达到了约2000亿元,预计到2025年将突破3000亿元大关。其中,休闲卤味以每年10%的速度持…...
自除数-C语言
描述 给定两个整数 left 和 right ,返回一个列表,列表的元素是范围 [left, right] 内所有的 自除数。 1 < left < right < 104 自除数 是指可以被它包含的每一位数整除的数,自除数 不允许包含 0 。例如,128 是一个 自除…...
-bash: ./startup.sh: Permission denied解决
今天在Linux上启动Tomcat,结果弹出:-bash: ./startup.sh: Permission denied 的提示。 这是因为用户没有权限,而导致无法执行。用命令chmod 修改一下bin目录下的.sh权限就可以了。 在Tomcat的bin目录下 ,输入命令行 :c…...
Java课题笔记~ AOP 概述
AOP 简介 AOP(Aspect Orient Programming)面向切面编程。 面向切面编程是从动态角度考虑程序运行过程。 AOP的底层,就是采用动态代理的方式实现的。 采用了两种代理:JDK动态代理、CGLIB动态代理。 JDK动态代理:使…...
真我V3 5G(RMX2200 RMX2201)解锁刷机全过程
安卓系统新Rom包为GSI,更具有通用性,可以比较放心刷。 原厂系统垃圾多、广告多,甚至热点功能不支持ipv6,严重偏离热点机的定位。 主要参考 https://www.bilibili.com/read/cv20730877/https://www.bilibili.com/read/cv2073087…...
springCache-缓存
SpringCache 简介:是一个框架,实现了基于注解的缓存功能,底层可以切换不同的cache的实现,具体是通过CacheManager接口实现 使用springcache,根据实现的缓存技术,如使用的redis,需要导入redis的依赖包 基于map缓存 …...
【solon生态】- solon.cloud.micrometer插件使用指南及micrometer详解
solon.cloud.micrometer插件使用指南 solon是什么solon的cloud生态图快速入门 micrometer指南micrometer是什么监控系统 Supported Monitoring Systems注册表 Registry度量 Meters度量名 Naming Meters度量标签 Tag Naming通用标签 Common Tags 指标过滤器 MeterFilter聚合速率…...
【Spring Boot】Thymeleaf模板引擎 — Thymeleaf的高级用法
Thymeleaf的高级用法 主要介绍Thymeleaf的内联、内置对象、内置变量等高级用法。 1.内联 虽然通过Thymeleaf中的标签属性已经几乎满足了开发中的所有需求,但是有些情况下需要在CSS或JS中访问后台返回的数据。所以Thymeleaf提供了th:inline"text/javascript/…...
用html+javascript打造公文一键排版系统13:增加半角字符和全角字符的相互转换功能
一、实践发现了bug和不足 今天用了公文一键排版系统对几个PDF文件格式的材料进行文字识别后再重新排版,处理效果还是相当不错的,节约了不少的时间。 但是也发现了三个需要改进的地方: (一)发现了两个bug:…...
元宇宙3D数字虚拟客服打造年轻化、数字化营销新品牌
融合了元宇宙、AI和云计算等技术的虚拟数字人,成为元宇宙数字内容交互的载体,将现实世界中的人与虚拟数字世界的场景、模型及产品链接起来,特别是为电力企业打造的电力元宇宙平台,带来营销宣传多重好处的同时,树立了数…...
micromamba快速安装(windows版本)
快速安装 Micromamba Micromamba 是一个静态链接的 C++ 可执行文件,在 Windows 上就是一个 micromamba.exe 文件,下载下来就直接可以用,甚至都不需要专门安装。唯一需要做的就是设置 Shell 的 Profile 文件,使 micromamba 成为可以在命令行里调用的一个命令。 Micromamba…...
HTML <source> 标签
实例 拥有两份源文件的音频播放器。浏览器应该选择它所支持的文件(如果有的话): <audio controls><source src="horse.ogg" type="audio/ogg"><source src="horse.mp3" type="audio/mpeg">Your browser does n…...
香港第一金:加息预期仍令贵金属承压,黄金仍需关注破位情况
香港第一金基本面分析: 中国纸黄金交易通显示,全球最大黄金上市交易基金(ETF)截至06月27日持仓量为925.66吨,较上日减持1.44吨,本月止净减持13.90吨。 周二美国公布的上月新屋销售飙升12.2%,经季节调整后折合成年率为…...
C语言学习笔记 vscode使用外部console-11
前言 在默认情况下,我们运行C语言程序都是在vscode终端的,在小程序运行时这个是没有问题的,但是当程序变得复杂它就不好用了,这时我们可以将这个终端设置为外部console,这样方便处理更多、更复杂的程序。 步骤 1.点击…...
96 | Python 小项目—— 学生成绩管理系统
文章目录 项目概述功能点2. 登录界面3. 主页面4. 数据录入界面5. 数据删除界面6. 数据修改界面7. 数据查询界面8. 成绩排名界面9. 成绩分析界面10. 学生信息查询界面11. 运行和测试总结项目概述 学生成绩管理系统是一个简单的学生课程管理系统,旨在帮助学校或教育机构轻松管理…...
【uniapp使用web-view点击返回报错后返回不了】
问题及解决 问题解决 问题 使用web-view跳转到别人的网站之后点击返回报错,返回不了 解决 使用以下方法 <template><view></view> </template> <script> var wv;//计划创建的webview export default {onLoad() {// #ifdef APP-PL…...
Map Reduce教程_编程入门自学教程_菜鸟教程-免费教程分享
教程简介 MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)",是它们的主要思想,都是从函数式编程语…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
