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

由于我们需要用状态来描述整个股票买卖的过程

因此我们不能简单的用「买入」和「卖出」来表示整个过程，因为这两个是动作，动作只会引起状态发生改变

正确的状态表示应该是「有股」和「无股」，前者用 1 后者用 0 表示

1 即可以自转一圈回到 1 ，也可以通过「卖出」走到 0

0 既可以自转一圈回到 0 ，也可以通过「买入」走到 1

因此当从 1 走到 0 时，需要加 $w[i]$；从 0 走到 1 时需要减 $w[i]$

状态表示为 $f[i,\ j,\ k]$ ，表示：走了 $i$ 步，在进行了 $j$ 次交易，处于状态 $k$ 的所有走法，属性为所有走法当中收益的最大值

前面提到，0 可以从 0 走来，也可以从 1 走来，因此有 $f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i])$

1 可以从 1 走来，也可以从 0 走来，因此有 $f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i])$

$j$ 表示的是已经进行的交易次数，因此从 0 走到 1 是一次新的交易，从 1 走到 0 不是新的交易

在初始化部分，我们需要初始化所有 $f[i][0][0]=0$ ，其余的全部为负无穷

这个是根据实际意义得处理的，即走了 $i$ 步，进行了 0 笔交易，处于状态 0 的收益，这个显然为 0

完整代码：

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

using namespace std;

const int N = 1e5 + 10, M = 110;

int w[N], f[N][M][2];
int n, k;

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