• 认为讲得不错的不妨支持一下

股票买卖

讲解股票买卖 II 至 VI 五道题目（$1055$ ~ $1059$），重点算法 状态机

传送门：

• 股票买卖II
• 股票买卖III
• 股票买卖IV
• 股票买卖V
• 股票买卖VI

股票买卖 II

题目描述

给定一个长度为 $N$ 的数组 $w$ ，$wi$ 表示第 $i$ 天股票价格

不能同时参与多笔交易，求最大利润。

状态转移

共有 $2$ 个状态，为 手中有货 与 手中无货 。

$4$ 种转移：

• 有 -> 有：搁置，暂不进行操作
• 有 -> 无：卖出，收益 $+wi$
• 无 -> 无：搁置，暂不进行操作
• 无 -> 有：买入，收益 $-wi$

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][2];
//f[i][0]表示在第i天手中有货的最大收益
//f[i][1]表示在第i天手中无货的最大收益

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    f[0][0] = -INF, f[0][1] = 0;
    //入口，在第一次计算下面第二个转移方程时会优先选择f[i - 1][1]，也就是搁置
    //因为第一次交易时手中没有货，肯定无法卖出
    for (int i = 1; i <= n; i ++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] - w[i]); //搁置与买入的最优策略
        f[i][1] = max(f[i - 1][1], f[i - 1][0] + w[i]); //搁置与卖出的最优策略
    }

    printf("%d\n", f[n][1]);

    return 0;
}

股票买卖 III

题目描述

给定一个长度为 $N$ 的数组 $w$ ，$wi$ 表示第 $i$ 天股票价格

你最多只能参与 $2$ 笔交易，且不能同时参与多笔交易，求最大利润。

状态转移

共有 $2$ 个状态，为 手中有货 与 手中无货 。

$4$ 种转移：

• 有 -> 有：搁置，暂不进行操作
• 有 -> 无：卖出，收益 $+wi$
• 无 -> 无：搁置，暂不进行操作
• 无 -> 有：买入，收益 $-wi$

唯一的区别就是这里需要做两次状态转移计算（代表两笔交易）

在计算时要注意交易的次数

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int w[N];
int f[N][3][2];
//f[i][j][0]表示在第i天，进行了j次交易后，手中有货时的最大收益
//f[i][j][1]表示在第i天，进行了j次交易后，手中无货时的最大收益

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    memset(f, -0x3f, sizeof(f));
    for (int i = 0; i <= n; i ++) f[i][0][0] = 0;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= 2; j ++)
        {
            //每一次买入算作每次新的交易的开始
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }

    int res = 0;
    for (int i = 0; i <= 2; i ++) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}

股票买卖 IV

题目描述

给定一个长度为 $N$ 的数组 $w$ ，$wi$ 表示第 $i$ 天股票价格

你最多只能参与 $m$ 笔交易，且不能同时参与多笔交易，求最大利润。

状态转移

共有 $2$ 个状态，为 手中有货 与 手中无货 。

$4$ 种转移：

• 有 -> 有：搁置，暂不进行操作
• 有 -> 无：卖出，收益 $+wi$
• 无 -> 无：搁置，暂不进行操作
• 无 -> 有：买入，收益 $-wi$

代码

//代码与上个题目几乎完全相同，将做两次计算转为了做k次计算
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N];
int f[N][M][2];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    memset(f, -0x3f, sizeof(f));
    for (int i = 0; i <= n; i ++) f[i][0][0] = 0;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }

    int res = 0;
    for (int i = 0; i <= m; i ++) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}

股票买卖 V

题目描述

给定一个长度为 $N$ 的数组 $w$ ，$wi$ 表示第 $i$ 天股票价格，

• 你每卖出一支股票，就会有一天的冷冻期（即第二天不能进行任何操作）
• 你不能同时参与多笔交易

求最大利润。

状态转移

共有 $3$ 个状态，为 手中有货 、 手中无货 与 冷冻期 。

$5$ 种转移：

• 有 -> 有：搁置，暂不进行操作
• 有 -> 冻：卖出，收益 $+wi$
• 无 -> 有：买入，收益 $-wi$
• 无 -> 无：搁置，暂不进行操作
• 冻 -> 无：冷冻期，不能进行操作

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][3];
//f[i][0]表示在第i天手中有货的最大收益
//f[i][1]表示在第i天处于冷冻期的最大收益
//f[i][2]表示在第i天手中无货的最大收益

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    f[0][0] = f[0][1] = -INF;
    f[0][2] = 0;

    for (int i = 1; i <= n; i ++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        //题目中“冷冻期”的设定较为特殊，因为其只能由卖出股票（有）转变而来
        f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }

    printf("%d\n", max(f[n][1], f[n][2]));

    return 0;
}

股票买卖 VI

题目描述

给定一个长度为 $N$ 的数组 $w$ ，$wi$ 表示第 $i$ 天股票价格，

给定手续费 $m$ ，每次交易（一次买入，一次卖出）都须支付手续费，

求最大利润。

状态转移

共有 $3$ 个状态，为 手中有货 、 手中无货 。

$4$ 种转移：

• 有 -> 有：搁置，暂不进行操作
• 有 -> 无：卖出，收益 $+wi-f$ ，因为要交手续费
• 无 -> 有：买入，收益 $-wi$
• 无 -> 无：搁置，暂不进行操作

只不过是 股票买卖 II 经过了微小改动而已，

亏它还是一道中等难度题

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;
int n, m;
int w[N];
int f[N][2];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    f[0][0] = -INF, f[0][1] = 0;
    for (int i = 1; i <= n; i ++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] - w[i]); //搁置与买入的最优策略
        f[i][1] = max(f[i - 1][1], f[i - 1][0] + w[i] - m);//搁置与卖出的最优策略
    }

    printf("%d\n", f[n][1]);

    return 0;
}