Acwing 1058 股票买卖V
题目传送门
一、画图分析状态机
二、状态分析
\(f[i][0]\) : 进行到第 \(i\) 天 并且 现在当前有股票买入
\(f[i][1]\) : 进行到第 \(i\) 天 并且 现在当前没有股票买入的第一天 (\(i-1\)天刚卖出股票)
\(f[i][2]\) : 进行到第 \(i\) 天 并且 现在当前没有股票买入的第 \(>=2\) 天
三、实现代码
#include
using namespace std;
const int N = 100010;
int n;
int w[N];
int f[N][3];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
//预求最大值,先设最小值
memset(f, -0x3f, sizeof f);
//入口,初始状态
f[0][2] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][2] - w[i], f[i - 1][0]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = max(f[i - 1][2], f[i - 1][1]);
}
//出口有两个,需要取一下最大值
cout << max(f[n][0], max(f[n][1], f[n][2])) << endl;
return 0;
}