1057. 股票买卖 IV

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易数量。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

1≤N≤105,
1≤k≤100

输入样例1：

3 2
2 4 1

输出样例1：

2

输入样例2：

6 2
3 2 6 5 0 3

输出样例2：

7

样例解释

样例1：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

样例2：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

思路:

/*注意：
这里状态机的过程，对于每个股票，要么就买，要么就卖，不能说是买了然后在同一个点直接卖掉，这样是不符合状态机模型的，因此对于上述转移方程可以会有人提出疑问。
为什么状态转移方程不能是下面代码，即卖的时候才算做了一次交易，原代码是买的时候才算一次交易f[i][j][0] = max(f[i - 1][j - 1][1] + w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][0] - w[i], f[i - 1][j][1]);
终究要回归到状态转移的起点，第一支股票只有买，和不买这两个操作，一定不可能是卖和不卖的这两个操作，因此第一支股票如果买入时，必须按照一次交易处理。否则如果第一次股票如果买入时，不按一次交易处理，也就代表着第一支股票卖出才算一次交易，也就代表着在第一支股票卖出之前还买了一支股票，显然是矛盾的。\初始化：
如果一种状态不合法，或者不希望从这个状态转移过来 ，那么就把它设成正无穷或负无穷
因为这个题要求最大值，所以把不合法的设成负无穷，也这样这个状态不可能用来更新后来的状态
例如这道题中f[i][0][1]表示，如果我们处理了0笔股票，并且我们手中居然还有票，这显然是不可能的如果我们处理了0笔股票并且目前手里没有票，那收入就是0，即f[i][0][0] = 0*/

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 110;int f[N][M][2];int n, m;int main()
{cin >> n >> m;memset(f, -0x3f, sizeof(f));for (int i = 0; i <= n; i++)f[i][0][0] = 0;for (int i = 1; i <= n; i++){int w;cin >> w;for (int j = 1; j <= m; j++){f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w);f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w);}}int res = 0;for (int i = 0; i <= m; i++)res = max(res, f[n][i][0]);cout << res;return 0;
}