我要评论题目：1057. 股票买卖 IV
分析：
我们假设每一次交易分为两个阶段，第一个阶段是先买入，第二个阶段是卖出。
设dp(i, j, 0)表示考虑前i天，在第j次交易中我们已经卖出（第j次交易已经完全完成），dp(i, j, 1)表示考虑前i天，在第j次交易中我们已经买入（第j次交易的第一个阶段完成）。
状态机模型如下
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
int dp[100010][110][2];
int n, k;
int main()
{
cin >> n >> k;
mem(dp, -inf);
for (int i = 0; i <= n; i++) dp[i][0][0] = 0;
for (int i = 1; i <= n; i++)
{
int val; cin >> val;
for (int j = 1; j <= k; j++)
{
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + val);
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - val);
}
}
int maxx = 0;
for(int j = 0; j <= k; j++)
maxx = max(maxx, dp[n][j][0]);
cout << maxx << endl;
}
题目：1058. 股票买卖 V
分析：
感觉状态机dp越来越有意思了…
我们设dp(i, j)表示考虑第i天结束时状态为j的时候，获得的最大利润。
j = 0表示有货，j = 1表示无货的第一天，j = 2表示无货的第N天(N
>
=
>=
>= 2)
再很重要的一点就是找好入口和出口，以便于准确无误的初始化。
因为i = 0的状态中只有j = 2合法（可以看成经过了很多天的无货状态）。
然后出口的话就很简单了，只有可能由状态1和状态2转出。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;
int dp[maxn][3];
int n;
int main()
{
cin >> n;
mem(dp, -inf);
dp[0][2] = 0;
for(int i = 1; i <= n; i++)
{
int val; cin >> val;
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - val);
dp[i][1] = max(dp[i - 1][0] + val, dp[i][1]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]);
}
cout << max(dp[n][1], dp[n][2]) << endl;
}
本文地址：https://blog.csdn.net/weixin_43987810/article/details/108586635
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论