股票买卖篇(II,III,IV)--基础,详细!状态机简单应用

news/2024/2/29 2:36:48

目录

股票买卖II

 本题思路

关于异常值的解释 

代码 

 股票买卖III

 本题思路 (包括对交易过程的理解,需认真理解)

代码

股票买卖 IV 

本题思路 

 代码


股票买卖II

 输入样例

6
7 1 5 3 6 4

输出样例

7

输入样例 

5
1 2 3 4 5

输出样例 

4

 本题思路

该题是最简单的一道题

从两个状态入手

0:在第i天手中没有股票

1:在第i天手中拥有股票

状态方程

①:f[i][0]=max(f[i-1][0],f[i-1][1]+a)

一个一个解释:

f[i][0]:在第i天手中没有股票的情况

f[i-1][0]:在第i-1天其实都没有

f[i-1][1]+a:在第i-1天拥有股票,说明是在第i天卖出了,所以要加上第i天股票的价格a

②:f[i][1]=max(f[i-1][1],f[i-1][0]-a)

一个一个解释:

f[i][1]:在第i天手中拥有股票的情况

f[i-1][1]:在第i-1天其实都有

f[i-1][0]-a:在第i-1天其实没有股票,说明是在第i天买入了,所以要减去第i天股票的价格a

关于异常值的解释 

由于要用到"i-1",这种(一般都需要特殊处理),会出现f[0][1]这样尴尬的现象

就相当于你没有物品,何谈拥有,亦或者,你都没有对象,何谈分手??🐕🐕

所以现在就要对其进行特殊的赋值,由于要算最大值,呢就赋值无穷小,怎么也不会被选中

代码 

// 两种情况
// 1.第i天手中是否有股票(0:没有,1:有)
// f[i][0]=max(f[i-1][0],f[i-1][1]+a)
// f[i][1]=max(f[i-1][1],f[i-1][0]-a)#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int f[N][2];
int n;int main()
{cin>>n;f[0][1]=-0x3f3f3f3f;//刚开始以为可以省略,但是//前i-1天不可能出现,f[0][1]的情况(//观察f[i][0]的状态如果这个不特殊处理,第一波就会出错)//但是会出现f[0][0]//而且一共1e5个数大小10000,然后f[0][1]就取4个3f//我第一次取得一个-0x3f,然后在第1000组数据就WA了for(int i=1;i<=n;i++){int a;scanf("%d",&a);f[i][0]=max(f[i-1][0],f[i-1][1]+a);f[i][1]=max(f[i-1][1],f[i-1][0]-a);}cout<<f[n][0];return 0;
}

小插曲:

如果以后特殊值处理情况下,都设成0x3f3f3f3f,这样至少不会出现让你找好久都不知道错哪里的乌龙 

 股票买卖III

输入样例: 

8
3 3 5 0 0 3 1 4

输出样例:

6

输入样例:

5
1 2 3 4 5

输出样例: 

4

 本题思路 (包括对交易过程的理解,需认真理解)

本题在上一题基础上添加了一个条件--只允许两次交易

首先,不着急聊状态,要先明白一个词"交易",什么叫做"交易"?

就是有买,有卖,才算一次交易

要理解,从1-->0,是拥有到没有的过程这是一次交易

0--->1--->0 是第 'j-1' 次交易完后是 '0' 的状态转移到第 'j' 次交易 '1' 的状态再到第 'j' 次交易 '0' 的状态

OK!如果上述过程理解了,就到状态解释了

还是两个状态:0/1(同上)

状态方程

①:f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+a)

一个一个解释:

f[i][j][0]:在第i天,进行第j次交易后,手中没有股票

f[i-1][j][0]:在第i-1天,进行第j次交易后,手中已经没有股票,在第i天没有进行交易,保持之前的状态(故:在第i天,仍是第j次交易)

f[i-1][j][1]+a:在第i-1天,进行第j次交易后,手中持有股票(但是这个为什么是j不是j-1呢?上面我说了,1-->0才是一次交易),本次是第j次交易的一半,所以在第i天卖出,加上a,这才是一次完整的交易

②:f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a)

f[i][j][1]:在第i天,进行第j次交易后,手中持有股票

f[i-1][j][1]:在第i-1天,进行第j次交易后,手中已经持有股票,在第i天没有进行交易,保持之前的状态

f[i-1][j-1][0]-a:在第i-1天,进行第j-1次交易时,手中卖掉了股票(1-->0这是完整的一次交易,故下次交易就是第j次,所以本次是第j次交易的开始,开始买入要减去本次的价格

好了话不多说

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N][3][2];
int n;int main()
{cin>>n;memset(f,-0x3f3f3f3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=n;i++){int a;scanf("%d",&a);f[i][0][0]=0;for(int k=1;k<=2;k++){f[i][k][0]=max(f[i-1][k][0],f[i-1][k][1]+a);f[i][k][1]=max(f[i-1][k][1],f[i-1][k-1][0]-a);}}int ma = -0x3f3f3f3f;for(int k = 0; k <= 2; k++){ma = max(ma, f[n][k][0]);}cout<<ma;return 0;
}

这里要说一点,为什么全都开始设为异常值了,开始我还是把最特殊的f[0][0][1]一个设置了异常处理,但是我发现不对,我看完别人的我发现,你一个交易是先1(买入)再(0),呢么你f[0][1][0],f[1][0][1]······要异常处理的太多了,不只是一个了,呢索性就都进行异常处理,然后把合理的置为0,f[0][0][0],f[1][0][0]·······都是合理的至为0

还有一个乌龙,我可能基础没学好我刚开始设置f[N][2][2],我以为就两次交易,的但是WA了,然后可能要存三个?迷迷,反正开三个对了,以后抽空研究一下,应该是存了“0,1,2”,所以开三个,以后都尽量开大一点,这种错磨人得很            

股票买卖 IV 

输入样例:

3 2
2 4 1

输出样例:

2

输入样例:

6 2
3 2 6 5 0 3

输出样例:

7

本题思路 

好吧,其实本题思路和上一个一模一样,就一点不一样,上一个是进行2次交易,本题是进行k次,就代码改一点进行,不懂私信我,或者什么的都行🙂🙂

 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N][110][3];int main()
{int n,k;cin>>n>>k;memset(f,-0x3f3f3f3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=n;i++){int a;scanf("%d",&a);f[i][0][0]=0;for(int j=1;j<=k;j++){f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+a);f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a);}}int ma=-0x3f3f3f3f;for(int j=0;j<=k;j++){ma=max(ma,f[n][j][0]);}cout<<ma;return 0;
}

好啦,总结一波,具体就是DP的子级,比DP要多考虑一个东西,就是状态,股票就是,是否持有股票(0/1)来作为两种状态 


https://www.jiucaihua.cn/news/show-4626276.html

相关文章

linux基础知识学习记录

这里写自定义目录标题 一、 计算机基础知识二 、 Linux操作系统的介绍三、 Linux的安装四、Linux命令使用汇总 一、 计算机基础知识 计算机组成&#xff1a;计算机主要硬件和软件2部分组成。计算机软硬件的概念&#xff1a;硬件是可以看得见的物理实体&#xff0c;软件是运行在…

Cubase12没有声音解决办法(Windows 11专用)

本文章由CSDN 不想加班呀 原创&#xff0c;转载请注明出处。 作者首页&#xff1a;不想加班呀的博客_CSDN博客-Python爬虫,电脑小知识,程序员剪视频领域博主 目录 前言 解决办法 第一步&#xff08;进入系统硬件和声音设置界面&#xff09; 第二步&#xff08;在声音设置中…

(学习日记)2023.04.27

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

柔性车间作业调度

1柔性车间作业调度 n n n个工件 { J 1 , J 2 , ⋯ , J n } \{J_1,J_2,\cdots,J_n\} {J1​,J2​,⋯,Jn​}要在 m m m台机器 { M 1 , M 2 , ⋯ , M m } \{M_1,M_2,\cdots,M_m\} {M1​,M2​,⋯,Mm​}上加工。每个工件包含一道或多道工序&#xff0c;工序顺序是预先确定的&#xf…

微信小程序获取手机号码 phonenumber.getPhoneNumber 提示47001错误

微信小程序获取手机号码 phonenumber.getPhoneNumber 提示47001错误 微信小程序获取客户端手机号码&#xff0c;踩的坑。如下提示&#xff1a; {"errcode":47001,"errmsg":"data format error hint: [6kMDxSDNRa-hAwqia] rid: 6308d1b5-69935bc9-1d9…

大数据:spark环境搭建,local模式,standalone模式,zookeeper standby,yarn模式

大数据&#xff1a;spark环境搭建&#xff0c;local模式 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;or…

大专毕业,从6个月开发转入测试岗位的一些感悟——写在测试岗位3年之际

时光飞逝&#xff0c;我从前端开发岗位转入测试岗位已经三年了&#xff0c;这期间从迷茫到熟悉&#xff0c;到强化&#xff0c;到熟练&#xff0c;到总结&#xff0c;感受还是很深的&#xff01; 三年前的某一个晚上&#xff0c;我正准备下班回家&#xff0c;我们的项目经理把…

初阶二叉树的相关性质定理及题目练习

前言&#xff1a; 前面我们介绍了初阶二叉树的相关知识&#xff0c;二叉树常考的还是链式二叉树&#xff0c;而且二叉树也会考很多选择题&#xff0c;本文重点是在给出一些常考的二叉树的性质定理推导和经典练习题目配合强化巩固知识。 目录 一、二叉树的常见性质定理 二、常…

我的测试之路:从入坑测试到月薪15k...

“干过保险卖过房&#xff0c;做过销售做过网管”这是我毕业后前两年的真实写照&#xff0c;因为所学网络安全专业不好找工作&#xff0c;毕业之后为了生活只能将就的干着这种门槛低的工作。后来一次同学聚会被同学带下坑后&#xff0c;正式转行软件测试。 刚入坑的两年&#…

复合型人才

一、为什么需要复合型人才 在社会的大环境影响下&#xff0c;不同行业所展现的交叉属性越来越强&#xff0c;因此单一型人才已经不满足当前的企业需求&#xff0c;复合型人才逐渐成为市场上的主流&#xff1a;即不仅要“精”通&#xff0c;更要“全”面。 人才需求是由市场的…