DP(动态规划求含有冻结期的买卖股票)-05-动态规划-买卖股票
2024-09-07 00:02:23
题目描述
Alice这次决定去股市里当一波韭菜。
她希望你设计一个算法,在满足以下3个约束条件下,计算出最大利润。
1、 你可以多次买卖一支股票,但是对于每支股票,你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
2、 因为周转资金需要时间,Alice在买入股票前(第一次除外)需要等一天的时间。即在卖出当天的后天才能进行下一次买入。
3、 为了方便计算,你不用考虑持股数、Alice是否买得起等问题。每次买卖获得的利润就是卖出价减去买入价。
她希望你设计一个算法,在满足以下3个约束条件下,计算出最大利润。
1、 你可以多次买卖一支股票,但是对于每支股票,你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
2、 因为周转资金需要时间,Alice在买入股票前(第一次除外)需要等一天的时间。即在卖出当天的后天才能进行下一次买入。
3、 为了方便计算,你不用考虑持股数、Alice是否买得起等问题。每次买卖获得的利润就是卖出价减去买入价。
输入
第一行股票样个数N(1<=N<=100),天数M(1<=M<=100)。
接下来N行每行包含M个整数,分别表示这只股票第i天的股价(1<=Pi<=10000)。
接下来N行每行包含M个整数,分别表示这只股票第i天的股价(1<=Pi<=10000)。
输出
输出一个数字,表示Alice的最大盈利。
样例输入 Copy
2 5
1 2 3 0 2
0 0 5 4 3
样例输出 Copy
8
提示
对于第一支股票会做两次买卖:
第一天买入,第二天卖出,盈利1元。
第四天买入(第三天筹集资金不能买入),第五天卖出,盈利2元。
对于第二支股票:
第一天或者第二天买入,第三天之后卖出,盈利5元。
一共盈利8元。
第一天买入,第二天卖出,盈利1元。
第四天买入(第三天筹集资金不能买入),第五天卖出,盈利2元。
对于第二支股票:
第一天或者第二天买入,第三天之后卖出,盈利5元。
一共盈利8元。
#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>
#include <cmath>
using namespace std;
int n,m;
int main(){
int sum = ;
cin>>n>>m;
vector<int>day(m);
vector<vector<int> >dp(m + ,vector<int>(,));;
while(n--){
dp[][] = INT_MIN;//第0天买入,防止后面跌的数字都比它大
dp[][] = dp[][] = ;//第0天买入,没有收益
for(int i = ;i < m;i++){
cin>>day[i];
}
for(int i = ;i <= m;i++){
//dp[i][0]存放第i天没卖股票的收益
//dp[i][1]存放第i天卖了股票的收益
//dp[i][2]存放第i - 1天卖了股票,第i天为冷冻期的收益 dp[i][] = max(dp[i - ][],dp[i - ][] - day[i - ]);
//今天的收益等于max(昨天没卖有股票,今天才买股票)
dp[i][] = day[i - ] + dp[i][];
//今天0点卖股票后的收益等于今天持有的股票收益加上昨天的股票价格
dp[i][] = max(dp[i - ][],dp[i - ][]);
//今天冷冻期的话,今天的收益等于今天0点买股票或者昨天0点买股票
}
sum += max(dp[m][],dp[m][]);
}
cout << sum <<endl;
return ;
}
最新文章
- 搭建 SubversionEdge for VS
- scanf函数与输入缓冲区
- java 滤镜实现
- 得到某个进程所有线程ID和入口地址
- jmeter 压力测试 参数
- LA-3135 - Argus(优先队列)
- pygtk手记(1)
- 字符串和整形数组的相互转化(JAVA程序)
- Spring 对缓存的抽象
- windows 下安装redis
- Redis——windows下如何连接Linux(centos7.x)虚拟机的Redis——【二】
- jsp界面的继承与否剖析
- SpringBatch的流程简介
- 51nod 1479 小Y的数论题
- linux常用命令:chown 命令
- 如何开启解决android studio的模拟器的问题
- selenium + python自动化测试unittest框架学习(七)随机生成姓名
- 2、Hive UDF编程实例
- IIS10搭建FTP服务
- TRANSLATE(转换大/小写并替换字符)