AcWing 1057. 股票买卖 IV
原题链接
中等
作者:
小.bug
,
2022-05-15 10:49:58
,
所有人可见
,
阅读 118
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 110;
int n, m;
int f[N][M][2];
int a[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[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]+a[i]);
f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);
}
}
int res = 0;
for(int i = 1; i <= m; i++) res = max(res,f[n][i][0]);
cout << res << endl;
return 0;
}