MLE暴力写法
/*
为什么状态转移方程是
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);
而不是
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + w);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w);
因为我们将一次完整的买入合卖出视作一次交易,只有当前一个状态是空仓,当前状态是持仓的时候,才视作开启了一次新的交易;
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 100010;
int f[N][110][2];
int w;
int n, k;
int ans;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> k;
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 <= k; 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);
}
}
for (int j = 0; j <= k; j++)
{
ans = max(ans, f[n][j][0]);
}
cout << ans << endl;
return 0;
}
利用取模进行滚动数组优化
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
int f[2][110][2];
int w;
int n, k;
int ans;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> k;
memset(f, -0x3f, sizeof(f));
f[0][0][0] = f[1][0][0] = 0;
for (int i = 1; i <= n; i++)
{
int w;
cin >> w;
for (int j = 1; j <= k; j++)
{
f[i % 2][j][0] = max(f[(i - 1) % 2][j][0], f[(i - 1) % 2][j][1] + w);
f[i % 2][j][1] = max(f[(i - 1) % 2][j][1], f[(i - 1) % 2][j - 1][0] - w);
}
}
for (int j = 0; j <= k; j++)
{
ans = max(ans, f[n % 2][j][0]);
}
cout << ans << endl;
return 0;
}
利用位运算进行滚动数组优化 比取模快100多ms
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
int f[2][110][2];
int w;
int n, k;
int ans;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> k;
memset(f, -0x3f, sizeof(f));
f[0][0][0] = f[1][0][0] = 0;
for (int i = 1; i <= n; i++)
{
int w;
cin >> w;
for (int j = 1; j <= k; j++)
{
f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1] + w);
f[i & 1][j][1] = max(f[(i - 1) & 1][j][1], f[(i - 1) & 1][j - 1][0] - w);
}
}
for (int j = 0; j <= k; j++)
{
ans = max(ans, f[n & 1][j][0]);
}
cout << ans << endl;
return 0;
}