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

【算法提高:动态规划】1.4 状态机模型 TODO

文章目录

  • 例题列表
    • 1049. 大盗阿福(其实就是打家劫舍)
    • 1057. 股票买卖 IV(k笔交易)
    • 1058. 股票买卖 V(冷冻期)
    • 1052. 设计密码⭐⭐⭐🚹🚹🚹(TODO)
    • 1053. 修复DNA🚹🚹🚹🚹🚹(TODO)

例题列表

1049. 大盗阿福(其实就是打家劫舍)

https://www.acwing.com/activity/content/problem/content/1287/
在这里插入图片描述

就是 打家劫舍 那道题。

对当前的房间选择 抢 或者 不抢。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int t = sin.nextInt();while (t-- != 0) {int n = sin.nextInt();int second = 0, pre = sin.nextInt();for (int i = 1; i < n; ++i) {int temp = pre;pre = Math.max(pre, second + sin.nextInt());second = temp;}System.out.println(pre);}}
}

1057. 股票买卖 IV(k笔交易)

https://www.acwing.com/problem/content/1059/

在这里插入图片描述

dp 数组多开一维表示第几笔交易就好了。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt(), k = sin.nextInt();int[] prices = new int[n];for (int i = 0; i < n; ++i) prices[i] = sin.nextInt();int[][] buy = new int[n][k], sell = new int[n][k];Arrays.fill(buy[0], -prices[0]);for (int i = 1; i < n; ++i) {buy[i][0] = Math.max(buy[i - 1][0], -prices[i]);sell[i][0] = Math.max(sell[i - 1][0], buy[i - 1][0] + prices[i]);for (int j = 1; j < k; ++j) {buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j - 1] - prices[i]);sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j] + prices[i]);}}System.out.println(sell[n - 1][k - 1]);}
}

1058. 股票买卖 V(冷冻期)

https://www.acwing.com/problem/content/1060/
在这里插入图片描述

限制 buy[i] 只能从 sell[i - 2] 转移过来就好了。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] buy = new int[n], sell = new int[n], prices = new int[n];for (int i = 0; i < n; ++i) prices[i] = sin.nextInt();buy[0] = -prices[0];buy[1] = Math.max(buy[0], -prices[1]);sell[1] = Math.max(sell[0], buy[0] + prices[1]);for (int i = 2; i < n; ++i) {buy[i] = Math.max(sell[i - 2] - prices[i], buy[i - 1]);sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);}System.out.println(sell[n - 1]);}
}

1052. 设计密码⭐⭐⭐🚹🚹🚹(TODO)

https://www.acwing.com/activity/content/problem/content/1290/

在这里插入图片描述
|T| + 1 个状态自动机。

在这里插入代码片

1053. 修复DNA🚹🚹🚹🚹🚹(TODO)

https://www.acwing.com/activity/content/problem/content/1291/

在这里插入图片描述

在这里插入代码片

相关文章:

【算法提高:动态规划】1.4 状态机模型 TODO

文章目录 例题列表1049. 大盗阿福&#xff08;其实就是打家劫舍&#xff09;1057. 股票买卖 IV&#xff08;k笔交易&#xff09;1058. 股票买卖 V&#xff08;冷冻期&#xff09;1052. 设计密码⭐⭐⭐&#x1f6b9;&#x1f6b9;&#x1f6b9;&#xff08;TODO&#xff09;1053…...

ip link add 命令

ip link add veth0 type veth peer name veth1 这条命令主要用于在 Linux 操作系统中创建一个新的 veth(虚拟以太网) 对&#xff0c;这是一种虚拟网络设备&#xff0c;用于在 Linux 命名空间&#xff08;namespaces&#xff09;之间创建网络连接。此命令将创建两个设备&#xf…...

unity事件处理

方法调用 //发送事件 【发送事件码&#xff0c;发送消息内容】 EventCenterUtil.Broadcast(EventCenterUtil.EventType.Joystick, ui);//监听无参事件 EventCenterUtil.AddListener(EventCenterUtil.EventType.Joystick, show); public void show(){}//发送事件 有参事件 Eve…...

《ChatGPT原理最佳解释,从根上理解ChatGPT》

【热点】 2022年11月30日&#xff0c;OpenAI发布ChatGPT&#xff08;全名&#xff1a;Chat Generative Pre-trained Transformer&#xff09;&#xff0c; 即聊天机器人程序 &#xff0c;开启AIGC的研究热潮。 ChatGPT是人工智能技术驱动的自然语言处理工具&#xff0c;它能够…...

大数据Flink(五十):流式计算简介

文章目录 流式计算简介 一、数据的时效性 二、流式计算和批量计算...

13-4_Qt 5.9 C++开发指南_基于QWaitCondition 的线程同步_Wait

在多线程的程序中&#xff0c;多个线程之间的同步实际上就是它们之间的协调问题。例如上一小节讲到的3个线程的例子中&#xff0c;假设 threadDAQ 写满一个缓冲区之后&#xff0c;threadShow 和 threadSaveFile 才能对缓冲区进行读操作。前面采用的互斥量和基于 OReadWriteLock…...

STM32(HAL)多串口进行重定向(printf函数发送数据)

目录 1、简介 2.1 基础配置 2.1.1 SYS配置 2.1.2 RCC配置 2.2 串口外设配置 2.3 项目生成 3、KEIL端程序整合 4、效果测试 1、简介 在HAL库中&#xff0c;常用的printf函数是无法使用的。本文通过重映射实现在HAL库多个串口可进行类似printf函数的操作。 2.1 基础配置 2.…...

29_互联网(The Internet)(IP数据包;UDP;TCP;DNS;OSI)

上篇介绍了计算机网络的基础知识&#xff0c;也提到互联网&#xff08;The Internet&#xff09;&#xff0c;本篇将会详细介绍互联网&#xff08;The Internet&#xff09;。 文章目录 1. 互联网&#xff08;The Internet&#xff09;组成及数据包传输过程2. IP 数据包的不足3…...

xShell常用命令

xShell常用命令 一、文件夹目录1、cd-更改目录2、mkdir-建立目录3、rm-删除目录4、pwd-查看当前路径5、rmdir-删除空目录 二、文件操作1、cat-显示文件内容2、diff-比较文件内容3、查看文件的名字和后缀4、ls-列出文件5、cp-复制文件6、mv-移动和重命名文件找不同&#xff1a;选…...

React性能优化之Memo、useMemo

文章目录 React.memo两种方式参数应用场景 拓展useMemouseMemo(calculateValue, dependencies) 参考资料 React.memo React 的渲染机制&#xff0c;组件内部的 state 或者 props 一旦发生修改&#xff0c;整个组件树都会被重新渲染一次&#xff0c;即时子组件的参数没有被修改&…...

IDEA开启并配置services窗口

前言&#xff1a; 一般一个spring cloud项目中大大小小存在几个十几个module编写具体的微服务项目。此时&#xff0c;如果要调试测需要依次启动各个项目比较麻烦。 方法一&#xff1a; 默认第一次打开项目的时候&#xff0c;idea会提示是否增加这个选项卡&#xff0c;如果你没…...

vue2企业级项目(三)

vue2企业级项目&#xff08;三&#xff09; 引入mockjs&#xff0c;i18n 1、mockjs 项目下载依赖 npm install --save-dev mock根目录创建mock文件夹&#xff0c;并创建mock/index.js import Mock from "mockjs";// 设置全局延时 没有延时的话有时候会检测不到数据…...

QT 在label上透明绘图

一、新建TransparentDemo工程 二、在界面上添加label&#xff0c;修改样式表&#xff0c;将底色置为红色&#xff0c;作为北京 三、新建一个TransparentLabel类&#xff0c;继承自QLabel 此时&#xff0c;工程包括文件 五、在transparentlabel.h中添加 头文件 #include …...

SAM(Segment Anything)大模型论文汇总

A Comprehensive Survey on Segment Anything Model for Vision and Beyond 论文&#xff1a;https://arxiv.org/abs/2305.08196 25页综述&#xff0c;198篇参考文献&#xff01;52个开源项目&#xff01;本文第一个全面回顾了分割一切模型(SAM)的研究和应用进展&#xff0c;…...

金融翻译难吗,如何做好金融翻译?

我们知道&#xff0c;金融翻译涉及企业经济这块的&#xff0c;是影响各公司发展很重要的一方面&#xff0c;翻译做得好&#xff0c;可以促进公司内外的交流&#xff0c;及时掌握各种信息&#xff0c;做好应对。那么&#xff0c;金融翻译难吗&#xff0c;如何做好金融翻译&#…...

Java面试题(Tomcat与Nginx)

Tomcat 什么是Tomcat&#xff1f; 简单来说是一个运行Java的网络服务器&#xff0c;也是jsp和serlvet的一个容器 Tomcat的缺省端口是多少&#xff0c;怎么修改? conf文件夹下修改server.xml文件 <Connector connectionTimeout"20000" port"8080" p…...

React-使用mobx

React 中使用 mobx 配置开发环境 安装mobx和中间件工具 mobx-react-lite 只能函数组件中使用 yarn add mobx mobx-react-lite初始化 mobx 定义数据状态 state在构造器中实现数据响应式处理 makeAutoObservble定义修改数据的函数 action实例化 store 并导出 import { compute…...

LeetCode ACM模式——哈希表篇(一)

刷题顺序及部分思路来源于代码随想录&#xff0c;网站地址&#xff1a;https://programmercarl.com 部分思路来源于力扣官方题解&#xff0c;作者主页&#xff1a;https://leetcode.cn/u/leetcode-solution/ 242. 有效的字母异位词 给定两个字符串 s 和 t &#xff0c;编写一个…...

WPF实战学习笔记31-登录界面全局通知

UI添加消息聚合器 <md:Snackbarx:Name"LoginSnakeBar"Grid.ColumnSpan"2"Panel.ZIndex"1"MessageQueue"{md:MessageQueue}" />注册提示消息 文件&#xff1a;Mytodo.Views.LoginView.cs构造函数添加内容 //注册提示消息 aggre…...

通用商城项目(中)

金山编译器出问题了。下面段落标号全出问题了&#xff0c;排版也出问题了。懒得改了。 使用对象存储OSS&#xff0c;保存品牌logo 新建Module&#xff0c;提供上传、显示服务 有些不明所以的&#xff0c;按照steinliving-commodity配置了一通pom.xml 新建application.yml&…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...