【算法|动态规划 | 线性dp | 状态机模型】AcWing1049. 大盗阿福 & 1058. 股票买卖 V & AcWing1059. 股票买卖 VI

目录

• 一、AcWing1049. 大盗阿福
• 二、AcWing1058. 股票买卖 V
• 三、AcWing1059. 股票买卖 VI

一、AcWing1049. 大盗阿福

原题链接：点击直接跳转到该题目

题目解析

我们本题用到了两个一维dp表分别是f[i]、g[i]

状态表示：

• f[i]：表示偷窃第i家所能窃取的最大值
• g[i]：表示不偷窃第i家所能窃取的最大值

状态转移方程：

• f[i] = max(g[i - 1] + arr[i])
• g[i] = max(f[i - 1],g[i - 1])

返回值：

• max(f[n],g[n])

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N  = 1e5 + 10;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int f[N],g[N],arr[N];
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++) cin >> arr[i];
        
        // dp初始化
        f[1] = arr[1];
        for(int i = 1;i <= n;i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1],g[i - 1]);
        }
        cout << max(f[n],g[n]) << endl;
    }
}

二、AcWing1058. 股票买卖 V

原题链接：点击直接跳转到该题目

题目解析

状态表示（dp[0/1/2][i]）：

• 0表示第i天结束后处于卖出状态，即手上没有股票
• 1表示第i天结束后处于买入状态，即手上右股票
• 2表示第i天结束后处于冷冻期（我们这里就可以理解为此时的第i天这一整天是处于冷冻期的）

返回值（结果值）：

• dp[0][n]

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

 - List item

const int N = 1e5 + 10;
int prices[N];
int dp[3][N]; // 0表示卖出状态，1表示买入状态，2表示冷冻期

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> prices[i];
    
    // dp初始化
    dp[1][1] = -prices[1];
    for(int i = 2;i <= n;i++) 
    {
        dp[0][i] = max(dp[0][i - 1],dp[1][i - 1] + prices[i]);
        dp[1][i] = max(dp[1][i - 1],dp[2][i - 1] - prices[i]);
        dp[2][i] = dp[0][i - 1];
    }
    printf("%d\n",dp[0][n]);
    return 0;
}

三、AcWing1059. 股票买卖 VI

原题链接：点击直接跳转到该题目

题目解析

状态表示：dp[0/1][i]，0表示第i天结束后没有手上没有股票；1表示第i天结束后手上有股票。

• dp[0][i]：表示第i天结束后手上没有股票的最大利益。
• dp[1][i]：表示第i天结束后手上有股票的最大利益。

状态转移方程：

• dp[0][i] = max(dp[0][i - 1],dp[1][i - 1]) + prices[i] - f
• dp[1][i] = max(dp[1][i - 1],dp[0][i - 1] - prices[i])

返回值（即最终结果值）：

• 由于最终手中一定是没有股票的，所以最后的结果值为dp[0][n]

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
int prices[N];
int dp[2][N];

int main()
{
    int n,f;
    scanf("%d %d",&n,&f);
    for(int i = 1;i <= n;i++) cin >> prices[i];
    dp[1][1] = -prices[1];
    for(int i = 2;i <= n;i++)
    {
        dp[0][i] = max(dp[0][i - 1],dp[1][i - 1] + prices[i] - f);
        dp[1][i] = max(dp[1][i - 1],dp[0][i - 1] - prices[i]);
    }
    printf("%d\n",dp[0][n]);
    return 0;
}