状态机模型

文章目录

    • 一、大盗阿福
    • 二、股票买卖 IV
    • 三、股票买卖 V
    • 四、设计密码
      • 4.1kmp题目
      • 4.2设计密码

一、大盗阿福

题目链接
在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N][2];
int main()
{int t, n;cin >> t;while(t --){cin >> n;for(int i = 1;i <= n;i ++){//f[i, 0]表示不抢第i家店铺//f[i ,1]表示要抢第i家店铺int money;cin >> money;f[i][0] = max(f[i - 1][0],f[i - 1][1]);f[i][1] = f[i - 1][0] + money;}printf("%d\n",max(f[n][0],f[n][1]));}return 0;
}

二、股票买卖 IV

题目链接
在这里插入图片描述
在这里插入图片描述

对于状态机模型来说,你刚开始所处的位置初始化为0(一般来说),其他位置一般初始化为无穷大,对于该题来说你要初始化为负无穷

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, INF = 1e9, M = 110;
int n,k;
int f[N][M][2];int main()
{cin >> n >> k;memset(f, -0x3f, sizeof f);for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;//j为0时代表你一次交易没有完成for(int i = 1;i <= n;i ++){int m;cin >> m;for(int j = 1;j <= k;j ++){f[i][j][0] = max(f[i - 1][j][1] + m, f[i - 1][j][0]);f[i][j][1] = max(f[i - 1][j - 1][0] - m,f[i - 1][j][1]);}}int res = 0;for(int i = 1;i <= k;i ++) res = max(res, f[n][i][0]);cout << res;return 0;
}

三、股票买卖 V

题目链接
在这里插入图片描述

这个题加了一个冷冻期的状态,其实和上一题差不多,没什么区别
多加了一种状态而已
入口是冷冻期

在这里插入图片描述

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N][3];
int n;int main()
{memset(f, -0x3f, sizeof f);f[0][2] = 0;//1代表你处于卖出状态,2代表你处于冷冻期cin >> n;for(int i = 1;i <= n;i ++ ){int w;cin >> w;f[i][0] = max(f[i - 1][2] - w, f[i - 1][0]);f[i][1] = f[i - 1][0] + w;f[i][2] = max(f[i - 1][1],f[i - 1][2]);}cout << max(f[n][1],f[n][2]);return 0;
}

四、设计密码

4.1kmp题目

这个题要用到kmp,先说说kmp,抽象理解,简写代码

具体理解请看我的这篇博客(kmp算法细节详解)

首先我们要理解kmp是算法的作用是进行子串的匹配,也就是根据子串的前缀和后缀最大能够匹配的字符串个数

图解:

在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int ne[N];int main()
{int n,m;cin >> n >> p + 1 >> m >> s + 1;//先求模式串next数组for(int i = 2, j = 0;i <= n;i ++){while(j && p[i] != p[j + 1]) j = ne[j];if(p[i] == p[j + 1]) j ++;ne[i] = j;//j 前面是前缀,后面到i是后缀}for(int i = 1, j = 0;i <= m;i ++)//遍历主串{while(j && s[i] != p[j + 1]) j = ne[j];if(s[i] == p[j + 1]) j ++;if(j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}

4.2设计密码

题目链接
在这里插入图片描述

题解摘自E.lena在这里插入图片描述在这里插入图片描述
在这里插入图片描述

这里f[i + 1][u] 为什么还要加上自己,因为这个f[i + 1][u] 可能含有由其他状态转移转移过来

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N=55,mod=1e9+7;int f[N][N],ne[N];
char str[N];//子串int main()
{int n,m;cin>>n>>str+1;m=strlen(str+1);for(int i=2,j=0;i<=m;i++)//求出ne数组(kmp模板){while(j&&str[j+1]!=str[i]) j=ne[j];if(str[j+1]==str[i]) j++;ne[i]=j;}f[0][0]=1;//已经匹配了0位,且匹配的子串的位置是0时的方案数为1;(初始化)for(int i=0;i<n;i++)//枚举密码位for(int j=0;j<m;j++)//把第i位密码匹配到的子串位置都枚举一遍//j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置for(char k='a';k<='z';k++)//把第i+1所有可能的字母都枚举一遍{//匹配过程:寻找当第i+1的位置是k时,并且密码已经生成了第i位,匹配的子串的位置是j时,能跳到哪个位置int u=j;while(u&&str[u+1]!=k) u=ne[u];if(str[u+1]==k) u++;if(u<m) f[i+1][u]=(f[i+1][u]+f[i][j])%mod;//因为是从f[i][j](i+1的位置为k)跳到f[i+1][u]这个位置,所以f[i+1][u]=f[i+1][u]+f[i][j];/*注:可能存在重边,因为j不同但ne[j]是相同的,并且k是相同的,所以此时f[i][j1]和f[i][j2]跳到的位置是一样的(k相同,ne[j1]=ne[j2])*/}int res=0;for(int i=0;i<m;i++) res=(res+f[n][i])%mod;//将所有的方案数加起来即为总方案数printf("%d",res);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/460550.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MATLAB——矩阵操作

内容源于b站清风数学建模 数学建模清风老师《MATLAB教程新手入门篇》https://www.bilibili.com/video/BV1dN4y1Q7Kt/ 目录 1.MATLAB中的向量 1.1向量创建方法 1.2向量元素的引用 1.3向量元素修改和删除 2.MATLAB矩阵操作 2.1矩阵创建方法 2.2矩阵元素的引用 2.3矩阵…

一:Linux学习笔记(第一阶段)-- 安装软件 vmware workstation 虚拟机软件 centos系统

目录 学习计划&#xff1a; 资源准备 虚拟机软件&#xff1a;就别自己找了 现在换网站了 下载比较费劲 Centos8&#xff1a; 阿里云镜像地址下载&#xff08;下载比较版 但是有不同版本&#xff09;&#xff1a;centos安装包下载_开源镜像站-阿里云 百度网盘地址&#xff…

如何在Linux系统中使用Zabbix进行监控

如何在Linux系统中使用Zabbix进行监控 Zabbix简介 安装Zabbix 在Debian/Ubuntu系统中安装 在CentOS/RHEL系统中安装 配置Zabbix数据库 创建数据库 导入数据库 配置Zabbix服务器 访问Zabbix Web界面 完成初始配置 配置Zabbix Agent 安装Agent 配置Agent 添加主机到Zabbix 创…

uniapp编译多端项目App、小程序,input框键盘输入后

项目场景&#xff1a; uniapp编译后的小程序端&#xff0c;app端 在一个输入框 输入消息后&#xff0c;点击键盘上的操作按钮之后键盘不被收起&#xff0c;点击其他发送按钮时&#xff0c;键盘也不被收起。 问题描述 在编译后的app上普通的事件绑定&#xff0c;tap,click在发…

代码随想录day15 二叉树(3)

文章目录 day11 栈与队列(2)栈与队列的总结 day13 二叉树&#xff08;1&#xff09;day14 二叉树&#xff08;2&#xff09;day15 二叉树&#xff08;3&#xff09; day11 栈与队列(2) 逆波兰表达式求值 https://leetcode.cn/problems/evaluate-reverse-polish-notation/ 逆…

【C#】搭建环境之CSharp+OpenCV

在我们使用C#编程中&#xff0c;对图片处理时会用到OpenCV库&#xff0c;以及其他视觉厂商提供的封装库&#xff0c;这里因为OpenCV是开源库&#xff0c;所以在VS资源里可以直接安装使用&#xff0c;这里简单说明一下搭建的步骤及实现效果&#xff0c;留存。 1. 项目创建 1.1…

环形运输距离Conveyor Belts

Conveyor Belts 题面翻译 传送带 题目描述 传送带 $ m_n $ 是一个大小为 $ n \times n $ 的矩阵&#xff0c;其中 $ n $ 是一个偶数。矩阵由顺时针移动的同心带组成。 换句话说&#xff0c;当 n 2 n2 n2 时&#xff0c;传送带矩阵就是一个 2 2 2 \times 2 22 的矩阵&a…

ffmpeg视频滤镜:添加边框-drawbox

滤镜介绍 drawbox 官网链接 > FFmpeg Filters Documentation 这个滤镜会给视频添加一个边框。 滤镜使用 参数 x <string> ..FV.....T. set horizontal position of the left box edge (default "0")y <string&…

CPU算法分析LiteAIServer视频智能分析平台噪声检测功能在视频监控中的应用与优势

在视频监控系统中&#xff0c;噪声问题一直是影响视频画面清晰度和可用性的关键因素。这些噪声可能源于多种因素&#xff0c;如低光环境、摄像机传感器的高灵敏度或编码压缩过程中的失真等。为了应对这些挑战&#xff0c;CPU算法分析LiteAIServer引入了噪声检测功能&#xff0c…

HTB:BoardLight[WriteUP]

目录 连接至HTB服务器并启动靶机 1.How many TCP ports are listening on BoardLight? 2.What is the domain name used by the box? 3.What is the name of the application running on a virtual host of board.htb? 4.What version of Dolibarr is running on Board…

mysql 5.7实现组内排序(连续xx天数)

需求&#xff1a;查询出连续登录的用户及其连续登录的天数 我先说一下思路&#xff1a;要实现连续登录的判断&#xff0c;可以找一下他们之间的规律。这里我拿一个用户来说&#xff0c;如果这个用户在1、2、3号都有登录记录&#xff0c;可以对这个用户的数据按照时间排序&…

★ Linux ★ 基础开发工具的使用(上)

Ciallo&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;我将和大家一起学习 linux 基础开发工具的使用~ 目录 壹 Linux编辑器 - vim使用 1.1 vim的基本概念 1.2 vim正常模式命令集 1.2.1 插入模式 1.2.2 移动光标命令 1.2.3 编辑命令 1.3 vim末行模式命令集 贰 Lin…

solidworks学习6吊环-20241030

solidworks学习6吊环 图 1 使用到的命名&#xff1a;拉伸曲面&#xff0c;旋转曲面&#xff0c;镜像实体&#xff0c;剪裁曲面&#xff0c; 前视基准面绘制 图 2 绘制旋转轴 图 3 旋转曲面 图 4 上视基准面绘制&#xff0c;标准圆边尺寸的时候需要按住shift键标注&#x…

提示词高级阶段学习day4.1

第一步&#xff1a;你要有一个大模型帐号&#xff0c;至少已经熟悉和它们对话的方式。最强性能当属ChatGPT4&#xff0c;当然也推荐国产平替&#xff1a; Kimi.ai - 帮你看更大的世界 智谱清言 第二步&#xff1a;看 OpenAI 的官方文档&#xff1a; 目录&#xff1a;OpenAI …

开源趣味艺术画板Paint Board

什么是 Paint Board &#xff1f; Paint Board 是简洁易用的 Web 端创意画板。它集成了多种创意画笔和绘画功能&#xff0c;支持形状绘制、橡皮擦、自定义画板等操作&#xff0c;并可以将作品保存为图片。 软件功能&#xff1a; 不过非常可惜&#xff0c;老苏最期待的数据同步还…

建设NFS服务器并实现文件共享

关闭防火墙和s0 systemctl stop firewalld setenforce 0 安装NFS yum install nfs-utils -y 新建共享目录并设置权限 echo "hello" > /nfs/shared/test1 chmod -Rf 777 /nfs/shared/ 配置服务端的NFS配置文件 vim /etc/exports /nfs/shared *(ro) 启动…

软件测试学习笔记丨SeleniumPO模式

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/22525 本文为霍格沃兹测试开发学社的学习经历分享&#xff0c;写出来分享给大家&#xff0c;希望有志同道合的小伙伴可以一起交流技术&#xff0c;一起进步~ 说明&#xff1a;本篇博客基于sel…

python通过keyboard库实现模拟/监听键盘

keyboard介绍 如果我们想要通过快捷键&#xff0c;来调用某段代码&#xff0c;我们可以使用python的keyboard库&#xff0c;这个库可以用于发送&#xff0c;挂钩&#xff0c;以及模拟键盘事件等&#xff0c;并且同时支持多种操作系统&#xff08;但是需要注意的是&#xff0c;…

Spring Boot 创建项目详细介绍

上篇文章简单介绍了 Spring Boot&#xff08;Spring Boot 详细简介&#xff01;&#xff09;&#xff0c;还没看到的读者&#xff0c;建议看看。 下面&#xff0c;介绍一下如何创建一个 Spring Boot 项目&#xff0c;以及自动生成的目录文件作用。 Maven 构建项目 访问 http…

windows下安装python库wordCloud报错

换电脑安装wordcloud半天安装失败&#xff0c;记录一下遇到的坑&#xff0c;也给大家节省点时间。 方法1&#xff1a; 错误呢就是下面这个&#xff0c;说没c编译器&#xff0c;要不就去他给的地址上安装一下&#xff0c;我安装了一下好像没什么用&#xff0c;也没太敢勾选&am…