[acwing面向模型编程]状态机模型

题目：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 clo() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define mem(a, b) memt(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 clo() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define mem(a高一物理公式大全, b) memt(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] = m长江之歌阅读答案ax(dp[i - endanger1][2], dp[i - 1][1]);    }    cout << max(dp[n][1], dp[n][2]) << endl;}

本文地址：https://blog.csdn.net/weixin_43987810/article/details/108586635