题目描述
可以选择在任意时间点买入股票,或者在手上有股票时卖出股票,在不超过k次交易后,最多获得多少钱?
算法1
(状态机dp)
本题中我们将购入商品作为一次交易的开始,认为存在两种状态,即有商品和无商品。
- 方程
- f[i][0] = max(f[i][0], f[i][1] + v[t])
- f[i][1] = max(f[i][1], f[i-1][0] - v[i])
- 前置条件
- memset(f, -0x3f, sizeof f)
- f[0][0] = 0
时间复杂度
O(n * k)
外层循环为天,因为前一天的交易不能在后一天的基础上。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i ++ )
#define ref(i, j, k) for(int i = j; i >= k; i -- )
const int N = 1e5 + 10, M = 66, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, f[N][2], a[N];
signed main()
{
//freopen("input.txt", "r", stdin);
cin >> n >> m;
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
f(i, 1, n)
cin >> a[i];
f(i, 1, n)
f(j, 1, m)
{
f[j][0] = max(f[j][0], f[j][1] + a[i]);
f[j][1] = max(f[j][1], f[j-1][0] - a[i]);
}
int res = 0;
f(i, 0, m)
res = max(res, f[i][0]);
cout << res << endl;
}