股票买卖

1054. 股票买卖

题目链接

1054. 股票买卖

给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

输入格式

第一行包含整数 \(N\)，表示数组长度。

第二行包含 \(N\) 个不大于 \(10^9\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5,\)

输入样例1：

6
7 1 5 3 6 4

输出样例1：

5

输入样例2：

5
7 6 4 3 1

输出样例2：

0

样例解释

样例1：在第 \(2\) 天（股票价格 = \(1\)）的时候买入，在第 \(5\) 天（股票价格 = \(6\)）的时候卖出，最大利润 = \(6-1 = 5\) 。注意利润不能是 \(7-1 = 6\), 因为你不能在买入股票前卖出股票。

样例2：在这种情况下, 不进行任何交易, 所以最大利润为 \(0\)。

解题思路

后缀最值

枚举选择买入第 \(i\) 天的股票以及选择 \(i\) 天后能卖出股票的最大收益

  • 时间复杂度：\(O(n)\)

代码

// Problem: 股票买卖
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1056/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,a[N],mx[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    mx[n]=a[n];
    for(int i=n-1;i;i--)mx[i]=max(a[i],mx[i+1]);
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,mx[i]-a[i]);
    cout<

1055. 股票买卖 II

题目链接

1055. 股票买卖 II

给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含整数 \(N\)，表示数组长度。

第二行包含 $$N 个不大于 \(10000\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5\)

输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

0

样例解释

样例1：在第 \(2\) 天（股票价格 = \(1\)）的时候买入，在第 \(3\) 天（股票价格 = \(5\)）的时候卖出, 这笔交易所能获得利润 = \(5-1 = 4\) 。随后，在第 \(4\) 天（股票价格 = \(3\)）的时候买入，在第 \(5\) 天（股票价格 = \(6\)）的时候卖出, 这笔交易所能获得利润 = \(6-3 = 3\) 。共得利润 \(4+3 = 7\)。

样例2：在第 \(1\) 天（股票价格 = \(1\)）的时候买入，在第 \(5\) 天 （股票价格 = \(5\)）的时候卖出, 这笔交易所能获得利润 = \(5-1 = 4\) 。注意你不能在第 \(1\) 天和第 \(2\) 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 \(0\)。

解题思路

状态机dp

  • 状态表示：

    • \(f[i][0]\) 表示前 \(i\) 天且第 \(i\) 天没有股票的最大利润
    • \(f[i][1]\) 表示前 \(i\) 天且第 \(i\) 天有股票的最大利润

  • 状态计算：

    • \(f[i][0]=max(f[i-1][0],f[i-1][1]+x)\)
    • \(f[i][1]=max(f[i-1][1],f[i-1][0]-x)\)

两种状态，即第 \(i\) 天是否有股票直接的转移，可能是同一种状态的转移，即状态里面保持有无股票不变，否则状态之间互相转移

  • 时间复杂度：\(O(n)\)

代码

// Problem: 股票买卖 II
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1057/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,a[N],f[N][2];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0][1]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
    	f[i][0]=max(f[i-1][0],f[i-1][1]+a[i]);
    	f[i][1]=max(f[i-1][1],f[i-1][0]-a[i]);
    }
    cout<

1056. 股票买卖 III

题目链接

1056. 股票买卖 III

给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含整数 \(N\)，表示数组长度。

第二行包含 \(N\) 个不大于 \(10^9\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5\)

输入样例1：

8
3 3 5 0 0 3 1 4

输出样例1：

6

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

0

样例解释

样例1：在第 \(4\) 天（股票价格 = \(0\)）的时候买入，在第 \(6\) 天（股票价格 = \(3\)）的时候卖出，这笔交易所能获得利润 = \(3-0 = 3\) 。随后，在第 \(7\) 天（股票价格 = \(1\)）的时候买入，在第 \(8\) 天 （股票价格 = \(4\)）的时候卖出，这笔交易所能获得利润 = \(4-1 = 3\) 。共得利润 \(3+3 = 6\)。

样例2：在第 \(1\) 天（股票价格 = \(1\)）的时候买入，在第 \(5\) 天 （股票价格 = \(5\)）的时候卖出, 这笔交易所能获得利润 = \(5-1 = 4\) 。注意你不能在第 \(1\) 天和第 \(2\) 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 \(0\)。

解题思路

前缀最值

设定两种单一交易：从某天开始交易最大的利润以及某天结束交易的最大利润。枚举结束交易的那天即可

  • 时间复杂度：\(O(n)\)

代码

// Problem: 股票买卖 III
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1058/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,f[2][N],a[N];
int main()
{
    int mn=0x3f3f3f3f;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	mn=min(mn,a[i]);
    	f[0][i]=max(f[0][i-1],a[i]-mn);
    }
    int mx=0;
    for(int i=n;i;i--)
    {
    	mx=max(mx,a[i]);
    	f[1][i]=max(f[1][i+1],mx-a[i]);
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[0][i]+f[1][i+1]);
    cout<

1057. 股票买卖 IV

题目链接

1057. 股票买卖 IV

给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 \(k\) 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 \(N\) 和 \(k\)，表示数组的长度以及你可以完成的最大交易数量。

第二行包含 \(N\) 个不超过 \(10000\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5,\)
\(1≤k≤100\)

输入样例1：

3 2
2 4 1

输出样例1：

2

输入样例2：

6 2
3 2 6 5 0 3

输出样例2：

7

样例解释

样例1：在第 \(1\) 天 (股票价格 = \(2\)) 的时候买入，在第 \(2\) 天 (股票价格 = \(4\)) 的时候卖出，这笔交易所能获得利润 = \(4-2 = 2\) 。

样例2：在第 \(2\) 天 (股票价格 = \(2\)) 的时候买入，在第 \(3\) 天 (股票价格 = \(6\)) 的时候卖出, 这笔交易所能获得利润 = \(6-2 = 4\) 。随后，在第 \(5\) 天 (股票价格 = \(0\)) 的时候买入，在第 \(6\) 天 (股票价格 = \(3\)) 的时候卖出, 这笔交易所能获得利润 = \(3-0 = 3\) 。共计利润 \(4+3 = 7\).

解题思路

状态机dp

  • 状态表示

    • \(f[i][j][0]\) 表示前 \(i\) 天交易了 \(j\) 次且第 \(i\) 天没有股票的最大利润
    • \(f[i][j][1]\) 表示前 \(i\) 天交易了 \(j\) 次且第 \(i\) 天有股票的最大利润

  • 状态计算：

    • \(f[i][j][0]=max(f[i-1][j][0],f[i-1][j-1][1]+x)\)
    • \(f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]-x)\)

状态转移类似，不过交易天数变化当且仅当交易完成时，同时可利用滚动数组优化空间

  • 时间复杂度：\(O(nk)\)

代码

// Problem: 股票买卖 IV
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1059/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e3+5;
int n,f[N][2],k,x;
int main()
{
    cin>>n>>k;
	memset(f,-0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		for(int j=0;j<=k;j++)
		{
			if(j)f[j][0]=max(f[j][0],f[j-1][1]+x);
			f[j][1]=max(f[j][1],f[j][0]-x);
		}
	}
	cout<

1058. 股票买卖 V

题目链接

1058. 股票买卖 V

给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 \(1\) 天)。

输入格式

第一行包含整数 \(N\)，表示数组长度。

第二行包含 \(N\) 个不超过 \(10000\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5\)

输入样例：

5
1 2 3 0 2

输出样例：

3

样例解释

对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 \(2-1 = 1\)，第二笔交易可得利润 \(2-0 = 2\)，共得利润 \(1+2 = 3\)。

解题思路

状态机dp

  • 状态表示：

    • \(f[i][0]\) 表示前 \(i\) 天且第 \(i\) 天没有股票且不处于冷冻期的最大利润
    • \(f[i][1]\) 表示前 \(i\) 天且第 \(i\) 天有股票的最大利润
    • \(f[i][2]\) 表示前 \(i\) 天且第 \(i\) 天处于冷冻期的最大利润

  • 状态计算：

    • \(f[i][0]=max(f[i-1][0],f[i-1][2])\)
    • \(f[i][1]=max(f[i-1][1],f[i-1][0]-x)\)
    • \(f[i][2]=f[i-1][1]+x\)

多了一个状态，冷冻期的前一天一定是有股票且当天卖出股票；没有股票且不处于冷冻期要么状态不变，要么前一天处于冷冻期；有股票要么状态不变要么前一天没有股票且不处于冷冻期

  • 时间复杂度：\(O(n)\)

代码

// Problem: 股票买卖 V
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1060/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,f[N][3],x;
int main()
{
    cin>>n;  
    cin>>x;
    f[1][1]=-x;
    for(int i=2;i<=n;i++)
    {
    	cin>>x;
    	f[i][0]=max(f[i-1][0],f[i-1][2]);
    	f[i][1]=max(f[i-1][1],f[i-1][0]-x);
    	f[i][2]=f[i-1][1]+x;
    }
    cout<

1059. 股票买卖 VI

题目链接

1059. 股票买卖 VI
给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格，再给定一个非负整数 \(f\)，表示交易股票的手续费用。

设计一个算法来计算你所能获取的最大利润。

你可以无限次地完成交易，但是你每次交易都需要支付手续费。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含两个整数 \(N\) 和 \(f\)，分别表示数组的长度以及每笔交易的手续费用。

第二行包含 \(N\) 个不超过 \(10000\) 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5,\)
\(1≤f≤10000\)

输入样例：

6 2
1 3 2 8 4 9

输出样例：

8

样例解释

在第 \(1\) 天（股票价格 = \(1\)）的时候买入，在第 \(4\) 天（股票价格 = \(8\)）的时候卖出，这笔交易所能获得利润 = \(8-1-2 = 5\) 。随后，在第 \(5\) 天（股票价格 = \(4\)）的时候买入，在第 \(6\) 天 （股票价格 = \(9\)）的时候卖出，这笔交易所能获得利润 = \(9-4-2 = 3\) 。共得利润 \(5+3 = 8\)。

解题思路

状态机dp

当交易完成时扣除手续费即可

  • 时间复杂度：\(O(n)\)

代码

// Problem: 股票买卖 VI
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1061/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,f[N][2],w,x;
int main()
{
    cin>>n>>w;
    cin>>x;
    f[1][1]=-x;
    for(int i=2;i<=n;i++)
    {
    	cin>>x;
    	f[i][0]=max(f[i-1][0],f[i-1][1]+x-w);
    	f[i][1]=max(f[i-1][1],f[i-1][0]-x);
    }
    cout<
模板前缀最值状态机dp

相关

题解 Count on a tree II/【模板】树分块

二分查找模板（准确找定值）

beautiful 模板

javascript模板字符串（反引号）

并查集模板

一个极短，极好记，常数小的行列式求值模板——qyy 行列式

设计模式之模板方法模式

模板

splay模板 指针版&splay被卡祭

考前复习 打打模板

Django模板层

excel批量按模板打印 vba经典

标签

一品网 冀ICP备14022925号-6