|
|
|
|
|
##[$AcWing$ $1058$. 股票买卖 $V$](https://www.acwing.com/problem/content/1060/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
给定一个长度为 $N$ 的数组 $w$，数组的第 $i$ 个元素 $w_i$ 表示第 $i$ 天的股票 **价格**
|
|
|
|
|
|
|
|
|
|
|
|
* **一次买入+一次卖出** 为一笔 **合法交易**，且 **不能同时产生多笔交易**（必须在再次购买前出售掉之前的股票）
|
|
|
|
|
|
|
|
|
|
|
|
* 卖出股票后，无法在第二天买入股票（冷冻期为$1$天）
|
|
|
|
|
|
|
|
|
|
|
|
设计一个**方案**，使得总利润 **最大**
|
|
|
|
|
|
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
第一行包含整数 $N$，表示数组长度。
|
|
|
|
|
|
|
|
|
|
|
|
第二行包含 $N$ 个不超过 $10000$ 的正整数，表示完整的数组。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
输出一个整数，表示最大利润。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$1≤N≤10^5$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
5
|
|
|
|
|
|
1 2 3 0 2
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
3
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**样例解释**
|
|
|
|
|
|
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 $2-1 = 1$，第二笔交易可得利润 $2-0 = 2$，共得利润 $1+2 = 3$。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 二、题目分析
|
|
|
|
|
|
以 **线性** 的方式 **动态规划**，考虑第 $i$ 天 的状态，需要记录的参数有哪些：
|
|
|
|
|
|
|
|
|
|
|
|
第 $i$ 天的 **决策状态**：
|
|
|
|
|
|
$j=0:$ 当前没有股票,且,不处于冷冻期 **空仓**
|
|
|
|
|
|
$j=1:$ 当前有股票 **持仓**
|
|
|
|
|
|
$j=2:$ 当前没有股票(当天卖出了股票)，处于 **冷冻期**
|
|
|
|
|
|
> **注意**： **冷冻期** 状态，现实含义是指当天卖出了股票，**后一天是没法交易**
|
|
|
|
|
|
|
|
|
|
|
|
### 三、状态机模型分析
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/07/03/55909_f22fdff4db-IMG_5D88B9FE2880-1.jpeg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
如果第 $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)$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
```
|
