题目描述
给定一个长度为 $N$ 的数组,数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润,你最多可以完成 $k$ 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。
输入格式
第一行包含整数 $N$ 和 $k$,表示数组的长度以及你可以完成的最大交易数量。
第二行包含 $N$ 个不超过 $10000$ 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
$ 1≤N≤10^5, \\ 1≤k≤100 $
样例
输入样例1:
3 2
2 4 1
输出样例1:
2
输入样例2:
6 2
3 2 6 5 0 3
输出样例2:
7
题解 状态机dp $O(nk)$
状态机dp。首先描述状态,我们可以用 $f(i, j)$ 表示状态,其中 $i$ 表示前 $i$ 天,而 $j$ 表示总共做了 $j$ 笔交易。每个状态还有两个子状态,表示是否持有股票,$1$ 表示持有,$0$ 表示不持有股票。
先给出状态转移方程, $a_i$ 表示第 $i$ 天的股价:
$$
f(i,j,0) = max(f(i - 1,j - 1,1) + a_i, f(i - 1,j,0)) \\\
f(i,j,1) = max(f(i - 1,j,1), f(i - 1,j,0) - a_i)
$$
这个状态转移方程是什么意思呢,先考虑不持有股票的状态,要么是前一天有股票并且今天卖了股票,要么是前一天不持有股票并且今天什么都没做,两种情况取最大值。再考虑持有股票状态,要么是前一天没有股票并且今天买了股票,要么是前一天有股票并且今天什么都没做,两种情况取最大值。
考虑到第一个状态转移中有 $j-1$,故需要分类讨论,当 $j=0$ 时,只有 $f(i,j,0) = f(i - 1,j,0)$。
要注意的是,一开始只有一种合法状态 $f(0, 0, 0) = 0$,其他状态都是不合法的,因为第零天不可能有股票,交易次数也只可能是0,所以其他状态都要赋值无限小。
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, M = 110;
// f[i][j][k] 表示在前i天,总共做了j笔交易时,持有或不持有股票时的最大收益
int f[N][M][2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
memset(f, -0x3f, sizeof(f));
f[0][0][0] = 0;
for (int i = 1; i <= n; i++)
{
int val;
cin >> val;
for (int j = 0; j <= k; j++)
{
if (j >= 1)
f[i][j][0] = max(f[i - 1][j - 1][1] + val, f[i - 1][j][0]);
else
f[i][j][0] = f[i - 1][j][0];
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - val);
}
}
int ans = 0;
for (int i = 0; i <= 100; i++)
for (int j = 0; j < 2; j++)
ans = max(ans, f[n][i][j]);
cout << ans;
}