[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 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