python/TangDou/AcWing/Statemachine/1058.md

##AcWing 1058. 股票买卖 V

一、题目描述

给定一个长度为 N 的数组 w，数组的第 i 个元素 w_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。

二、题目分析

以 线性 的方式 动态规划，考虑第 i 天 的状态，需要记录的参数有哪些：

第 i 天的 决策状态： j=0: 当前没有股票,且,不处于冷冻期 空仓 j=1: 当前有股票 持仓 j=2: 当前没有股票(当天卖出了股票)，处于 冷冻期

注意： 冷冻期 状态，现实含义是指当天卖出了股票，后一天是没法交易

三、状态机模型分析

如果第 i 天是 空仓 j=0 状态，则 i-1 天可能是 空仓 j=0 或 冷冻期 j=2 的状态

如果第 i 天是 持仓 j=1 状态，则 i-1 天可能是 持仓 j=1 状态 或 空仓 j=0 的状态,在第i天选择了买入

如果第 i 天是 冷冻期 j=2 状态，则 i-1 天只可能是 持仓 j=1 状态，在第 i 天选择了 卖出

闫氏DP分析法

状态表示f[i][j]属性: 考虑前 i 天股市，当前第 i 天的状态是 j 的方案

状态表示f[i][j]集合: Max(方案的总利润)

状态计算f[i][j]

 \large
\left\{\begin{array}{l} f[i][0]=max(f[i-1][0],f[i-1][2])
\\ f[i][1]=max(f[i-1][1],f[i-1][0]-w_i)
\\ f[i][2]=f[i-1][1]+w_i
\end{array}\right.

初始状态： f[i][0]=0 , 其它的状态初始化为-INF

目标状态： f[n][j]其中j=0,2

Code

时间复杂度： O(N) 空间复杂度： O(N)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n;
int w[N];
int f[N][3];

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;
    //开始进行状态转移
    for (int i = 1; i <= n; ++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] - w[i]);
        f[i][2] = f[i - 1][1] + w[i];
    }
    printf("%d\n", max(f[n][0], f[n][2]));
    return 0;
}