状态自动机

1.交易规则: 必须在再次购买之前出售所有的股票

2.定义状态: f[i][j][0]在前 i 天完成 j 次交易后的空方的现金;
f[i][j][1]在前 i 天完成 j-1 次交易并在第 i 天正进行第 j 次交易后多方的现金,

注意1

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]); 
//为什么是f[i-1][j-1][0]

//根据定义 
//f[i][j-1][0] 在前 i 天完成 j-1 次交易后的空方的现金， 减去第j次交易付出的现金w[i]
//f[i][j][1] 在前 i 天完成 j-1 次交易并在第 i 天进行第 j 次交易后多方方的现金

3.状态转移: 空方状态 (空 -> 空 或者 多 ->空)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])

4.计算结果: 枚举f[n][j][0]的最大值

初始化

如果一种状态不合法，或者不希望从这个状态转移过来 ，那么就把它设成正无穷或负无穷
因为这个题要求最大值，所以把不合法的设成负无穷，也这样这个状态不可能用来更新后来的状态

注意2

memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i++) f[i][0][0] = 0;

//例如这道题中 f[i][0][1] 表示，如果我们处理了0笔股票，并且我们手中居然还有票，这显然是不可能的，
//所以 f[i][0][1]=-INF;

//如果我们处理了0笔股票并且目前手里没有票，那收入就是0，即 f[i][0][0] = 0 

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5 + 10, M = 110;
int f[N][M][2], w[N];

int n, m;

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