DP(动态规划求含有冻结期的买卖股票)-05-动态规划-买卖股票-布布扣-bubuko.com

题目描述

Alice这次决定去股市里当一波韭菜。
她希望你设计一个算法，在满足以下3个约束条件下，计算出最大利润。
1、你可以多次买卖一支股票，但是对于每支股票，你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
2、因为周转资金需要时间，Alice在买入股票前（第一次除外）需要等一天的时间。即在卖出当天的后天才能进行下一次买入。
3、为了方便计算，你不用考虑持股数、Alice是否买得起等问题。每次买卖获得的利润就是卖出价减去买入价。

输入

第一行股票样个数N(1<=N<=100)，天数M(1<=M<=100)。
接下来N行每行包含M个整数，分别表示这只股票第i天的股价(1<=Pi<=10000)。

输出

输出一个数字，表示Alice的最大盈利。

样例输入 Copy

2 5
1 2 3 0 2
0 0 5 4 3

样例输出 Copy

提示

对于第一支股票会做两次买卖：
        第一天买入，第二天卖出，盈利1元。
        第四天买入(第三天筹集资金不能买入)，第五天卖出，盈利2元。
对于第二支股票：
        第一天或者第二天买入，第三天之后卖出，盈利5元。
一共盈利8元。

 1 #include <iostream>
 2 #include <vector>
 3 #include <stdio.h>
 4 #include <queue>
 5 #include <cmath>
 6 using namespace std;
 7 int n,m;
 8 int main(){
 9     int sum = 0;
10     cin>>n>>m;
11     vector<int>day(m);
12     vector<vector<int> >dp(m + 1,vector<int>(3,0));;
13     while(n--){
14         dp[0][0] = INT_MIN;//第0天买入，防止后面跌的数字都比它大
15         dp[0][1] = dp[0][2] = 0;//第0天买入，没有收益
16         for(int i = 0;i < m;i++){
17             cin>>day[i];
18         }
19         for(int i = 1;i <= m;i++){
20             //dp[i][0]存放第i天没卖股票的收益
21             //dp[i][1]存放第i天卖了股票的收益
22             //dp[i][2]存放第i - 1天卖了股票，第i天为冷冻期的收益
23 
24             dp[i][0] = max(dp[i - 1][0],dp[i - 1][2] - day[i - 1]);
25             //今天的收益等于max(昨天没卖有股票，今天才买股票)
26             dp[i][1] = day[i - 1] + dp[i][0];
27             //今天0点卖股票后的收益等于今天持有的股票收益加上昨天的股票价格
28             dp[i][2] = max(dp[i - 1][1],dp[i - 1][2]);
29             //今天冷冻期的话，今天的收益等于今天0点买股票或者昨天0点买股票
30         }
31         sum += max(dp[m][1],dp[m][2]);
32     }
33     cout << sum <<endl;
34     return 0;
35 }

DP(动态规划求含有冻结期的买卖股票)-05-动态规划-买卖股票

原文：https://www.cnblogs.com/qinqin-me/p/12256704.html