$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题相比于 AcWing 1057. 股票买卖 IV 多了一个状态

那道题能做这道题也一样能做

我们用 0 表示「有股」，1 表示「无股第一天」，2 表示「无股 $\ge 2$ 天」

$f[i][j]$ 表示：走了 $i$ 步，位于状态 $j$ 的所有不同走法，属性为收益的最大值，显然有：

$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])$

完整代码：

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

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int w[N];
int f[N][3];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    f[0][2] = 0, f[0][0] = f[0][1] = -INF;
    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]);
    }
    cout << max(f[n][1], f[n][2]) << endl;
    return 0;
}