您现在的位置是:首页 >技术教程 >动态规划-状态机模型网站首页技术教程

动态规划-状态机模型

重生之我是cxk 2024-06-17 11:19:19
简介动态规划-状态机模型

大盗阿福

题目

链接:https://www.acwing.com/problem/content/1051/

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N N N 家店铺,每家店中都有一些现金。

阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。

他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入格式

输入的第一行是一个整数 T T T,表示一共有 T T T 组数据。

接下来的每组数据,第一行是一个整数 N N N ,表示一共有 N N N 家店铺。

第二行是 N N N 个被空格分开的正整数,表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

输出格式

对于每组数据,输出一行。

该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

1 ≤ T ≤ 50 1 le T le 50 1T50,
1 ≤ N ≤ 1 0 5 1 le N le 10^5 1N105

输入样例:

2
3
1 8 2
4
10 7 6 14

输出样例:

8
24

样例解释

对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。

对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。

思路-动态规划

动态规划:

  • 状态表示:f[i]表示前i家的最大收益

  • 状态计算:

    • 抢劫第i家店铺:f[i-2]+w[i]
    • 不抢劫第i家店铺:f[i-1]

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i]= max(f[i-1],f[i-2]+a[i]);
    }
    cout<<f[n]<<endl;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

思路-状态机

状态机:

  • 状态表示:f[i,0],f[i,1]表示所有走了i步,且当前位于状态j的所有走法的集合的最大值

  • 状态计算:

    • 如果偷第i家,则第i-1家不能被偷:f[i,1]=f[i-1,0]+w[i]
    • 如果不偷第i家,则第i-1家任意安排:f[i,0]=max(f[i-1,1],f[i-1,0])
  • 最后结果为max(f[n][0],f[n][1])

状态机图:

image-20230519201339018

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> f(n + 1, vector<int>(2));
    f[1][0] = 0, f[1][1] = a[1];
    for (int i = 2; i <= n; i++) {
        f[i][0] = max(f[i - 1][1], f[i - 1][0]);
        f[i][1] = f[i - 1][0] + a[i];
    }
    cout<<max(f[n][0],f[n][1])<<endl;

}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

股票买卖 IV-k笔交易

题目

链接:https://www.acwing.com/problem/content/1059/

给定一个长度为 N N N 的数组,数组中的第 i i i 个数字表示一个给定股票在第 i i i 天的价格。

设计一个算法来计算你所能获取的最大利润,你最多可以完成 k k k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 N N N k k k,表示数组的长度以及你可以完成的最大交易笔数。

第二行包含 N N N 个不超过 10000 10000 10000 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

1 ≤ N ≤ 1 0 5 1 le N le 10^5 1N105,
1 ≤ k ≤ 100 1 le k le 100 1k100

输入样例1:

3 2
2 4 1

输出样例1:

2

输入样例2:

6 2
3 2 6 5 0 3

输出样例2:

7

样例解释

样例1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

样例2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

思路

状态机:

  • 状态表示:f[i,j,k]表示所有从前i个物品中选,进行了j次交易,且当前状态是k的所有选法的最大值

    • 当前持有股票【k=1】,当前没有股票【k=0】
    • 例如:f[i,j,0]表示前i天买卖了j次,当前手中无票,能获得的最大收益
    • f[i,j,1]表示前i天买卖进行了j次,当前手中有票,能获得的最大收益。
  • i天状态是持仓状态k=1),则第 i天可能产生的行为是 第i-1天买入行为 或 第i-1 天 持仓行为

    • f[i,j,1]=max(f[i-1,j,1],f[i-1,j-1,0]-w[i])
  • i 天状态是空仓状态(k=0),则第i天可能产生的行为是 第i-1天卖出行为 或 第i-1 空仓行为

    • f[i,j,0]=max(f[i-1,j,0],f[i-1,j,1]+w[i])

注意边界问题:

边界的初值首先要明白变量的取值范围 i ∈ [ 1 , n ] , j ∈ [ 1 , k ] iin[1,n],jin[1,k] i[1,n],j[1,k],在边界之外的需要设置处置,例如第0天

第0天:f[0,j,0]=0,f[0,j,1]=-INF为什么设置为负无穷:因为第零天不可以持仓,这是一个非法的行为

第0笔:f[i,0,0]=0

如果问题求最大值,则可以把非法的赋值为负无穷,最小值同理

状态机模型:

image-20230519223911253

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int f[N][110][2];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) f[0][i][1] = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);//前一天空仓或者卖出
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - a[i]);
        }
    }
  	cout<<f[n][k][0]<<endl;
    return 0;
}

可以像01背包一样将空间优化掉一维:

image-20230519223833896

股票买卖V-冷冻期

题目

链接:https://www.acwing.com/problem/content/1060/

给定一个长度为 N N N 的数组,数组中的第 i i i 个数字表示一个给定股票在第 i i i 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 1 1 天)。

输入格式

第一行包含整数 N,表示数组长度。

第二行包含 N N N 个不超过 10000 10000 10000 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

1 ≤ N ≤ 1 0 5 1 le N le 10^5 1N105

输入样例:

5
1 2 3 0 2

输出样例:

3

样例解释

对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。

思路

显然有三种状态:

f[i,1]表示第i天手中有票能获取的最大利润

f[i,0]表示卖出股票的第一天能获取的最大利润

f[i,2]表示卖出股票的第二天及以后能获取的最大利润

状态计算:

  • f[i,1]=max(f[i-1][1],f[i-1][2]-w[i])
  • f[i,0]=f[i-1][1]+w[i]
  • f[i,2]=max(f[i-1][0],f[i-1][2])

边界条件:

  • f[0][1]=-inf因为第0天不可能存在持有股票状态,因为前面没有天数可以买
  • f[0][0]=-inf因为第0天不可能是卖出股票的第一天
  • f[0][2]=0

状态机模型:

image-20230519225847438

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n;
    cin >> n;
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i];
    vector<vector<int>> f(n + 1, vector<int>(3));

    f[0][1] = f[0][0] = -INT_MAX;
    for (int i = 1; i <= n; i++) {
        f[i][1] = max(f[i - 1][1], f[i - 1][2] - w[i]);
        f[i][0] = f[i - 1][1] + w[i];
        f[i][2] = max(f[i - 1][0], f[i - 1][2]);
    }
    cout<<max(f[n][0],f[n][2])<<endl;

    return 0;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。