当前位置：首页 > news >正文

数据结构与算法学习笔记(Acwing 提高课)----动态规划·状态机模型

news 来源：原创 2025/7/15 22:31:16

数据结构与算法学习笔记----动态规划·状态机模型

@@ author: 明月清了个风
@@ first publish time: 2025.5.20

ps⭐️背包终于结束了，状态机模型题目不多。状态机其实是一种另类的状态表示方法，将某一个点扩展为一个状态进行保存并在多个状态之间转移，具体的来看题目理解吧。

Acwing 1049. 大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有$N $家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式

输入的第一行是一个整数 $T$ ，表示一共有 $T$ 组数据。
接下来的每组数据，第一行是一个整数 $N$ ，表示一共有N家店铺。第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。

输出格式

对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

$\le T \le 50$ ,

$\le N \le 100000$

思路

很明显，这道题是一道线性的问题，题目并没有对抢劫的顺序有特殊的规定，因此可以从前往后。

对于状态表示而言，使用 $f [i]$ 表示抢劫前 $i$ 家店的最大收益。

然后就是状态划分，同样根据最后一步的选择进行，若不抢劫第 $i$ 家店铺，那就是 $f [i - 1]$ ，若抢劫第 $i$ 家店铺，那么意味着第 $i - 1$ 家店铺就无法选择了，因此相当于只能从前 $i - 2$ 家店铺进行选择的最大值 $f [i - 2] + w [i]$ 。

但是上述分析其实在更新一个状态时，用到了前面两次的状态，下面考虑如何进行优化。

在上面的分析中，当仅用上一轮的状态也就是不知道第 $i - 2$ 的状态，如果我们抢劫第 $i$ 家店铺的时候，无法知道在最优解中第 $i - 1$ 家店铺是否被抢劫了，无法进行转移，因此引入状态机的表示方法，将所有状态表示为 $f [i] [0]$ 与 $f [i] [1]$ ， $0$ 表示当前店铺未选择， $1$ 表示当前店铺被选择了，这样就将每个店铺的两个状态分开了，对于 $f [i] [0]$ ,表示第 $i$ 个店铺没有被选择，因此可以从 $f [i - 1] [1]$ 或 $f [i - 1] [0]$ 转移过来；对于 $f [i] [1]$ ，表示第 $i$ 个店铺被选择了，因此只能从 $f [i - 1] [0]$ 转移过来。

代码

#include <iostream>
#include <cstring>using namespace std;const int N = 10010, inf = 0x3f3f3f3f;int T;
int n;
int f[N][2];
int w[N];int main()
{cin >> T;while(T --){cin >> n;for(int i = 1; i <= n; i ++) cin >> w[i];f[0][0] = 0, f[0][1] = -0x3f3f3f3f;for(int i = 1; i <= n; i ++){f[i][0] = max(f[i - 1][0], f[i - 1][1]);f[i][1] = f[i - 1][0] + w[i];}cout << max(f[n][1], f[n][0]) << endl;}return 0;
}

Acwing 1057. 股票买卖 IV

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

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

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

输入格式

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

第二行包含 $N$ 个不超过 $10000$ 的非负整数，表示完整的数组。

输出格式

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

数据范围

$\le N \le 10^5$ ,

$\le k \le 100$

思路

这道题很明显也可以看成两个状态，一个是手中有股票(已经买入了一个股票)，另一个是手中没有股票(可以买入一个股票)，那么状态的转移是：手中有股票时可以卖出不可以再次买入，也可以什么都不做；手中无股票时可以买入不可以卖出，也可以什么都不做。

当在某一天要卖出股票时，相当于获得这一天的权重 $w [i]$ ；当要在某一天买入时，就要减去当天的权重 $w [i]$ 。

搞清楚题目的意思后，可以看状态表示了，使用 $f [i] [j] [0]$ 和 $f [i] [j] [1]$ 表示前 $i$ 天完成了 $j$ 笔交易且当前的状态为 $0$ 或 $1$ 。 $0$ 表示手中没有股票， $1$ 表示手中有股票，也就是正在进行第 $j$ 次交易，属性就是集合的最大值。

那么对于状态转移， $f [i] [j] [0]$ 可以从 $f [i - 1] [j] [0]$ 走过来，也可以从 $f [i - 1] [j] [1]$ 转移过来，因此 $f [i] [j] [0] = ma x (f [i - 1] [j] [0], f [i - 1] [j] [1] + w [i])$ ；对于 $f [i] [j] [1]$ 来说，其状态转移方程为 $f [i] [j] [1] = ma x (f [i - 1] [j] [1], f [i - 1 [j - 1] [0]] - w [i])$ .

需要注意的是初始化状态，当交易次数为 $0$ 的时候，手中不可能持有股票，因此都为非法状态，需要进行标记，而交易次数为 $0$ 时，手中没有股票为合法状态，初始化为 $0$ 即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010, M = 110;int n, m;
int w[N];
int f[N][M][2];int main()
{cin >>  n >> m;for(int i = 1; i <= n; i ++) cin >> w[i];memset(f, -0x3f, sizeof f);for(int i = 0; i <= n; i ++) f[i][0][0] = 0;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);}}int res = 0;for(int i = 1; i <= m; i ++) res = max(res, f[n][i][0]);cout << res << endl;return 0;
}

Acwing 1058. 股票买卖V

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

设计一个算法来计算你所能获取的最大利润，在满足以下约束条件下，你可以尽可能地完成更多的交易(多次买卖一只股票)

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

输入格式

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

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

输出格式

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

数据范围

$\le N \le 10^5$ ,

思路

在这一题中添加了一个条件，在交易过后会有一天的冷冻期，因此变成了三个状态：手中有股票，手中没有股票的第一天，手中没有股票的第 $\ge 2$ 天。相当于把上一题中的第二个状态再次进行了分割。

这三个状态的转换关系如下：

手中有货可由手中有货转移而来，他可转移至手中无货的第一天(即第二种状态)，手中无货的第一天只能向第三种状态进行转移；第三种状态可以转移到自身，也可转移到手中有货(即第一种状态)。

同样地，可以使用 $f [i] [0], f [i] [1], f [i] [2]$ 表示这三种状态，三种状态的转移方程如下：
$f [i] [0] = ma x (f [i - 1] [0], f [i - 1] [2] - w [i])$

$f [i] [1] = f [i - 1] [0] + w [i]$

$f [i] [2] = ma x (f [i - 1] [1], f [i - 1] [2])$

然后就是考虑初始化的问题，前两个状态在刚开始时都是非法状态，即 $f [0] [0], f [0] [1]$ ；只要将 $f [0] [2]$ 初始化为 $0$ 即可。

还有一个情况就是数据是单调下降的，也就是股票一直在跌，最优解就是什么都不做，因此最后的答案可能出现在 $f [n] [1]$ 与 $f [n] [2]$ 中。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010, inf = 0x3f3f3f3f;int n;
int w[N];
int f[N][3];int main()
{cin >> n;for(int  i = 1; i <= n; i ++) cin >> w[i];f[0][0] = f[0][1] = -inf;f[0][2] = 0;for(int i = 1; i <= n; i ++){f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);f[i][1] = f[i - ][0] + w[i];f[i][2] = max(f[i - 1][1], f[i - 1][2]);}cout << max(f[n][1], f[n][2]) << endl;return 0;
}

Acwing 1052. 设计密码

你现在需要设计一个密码 $S$ ， $S$ 需满足：

$S$ 的长度是 $N$ ；
$S$ 只包含小写英文字母；
$S$ 不包含子串 $T$ ；

例如， $ab c$ 是 $ab c d e$ 的子串， $ab d$ 不是 $ab c d e$ 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 $10^9 + 7$ 的余数。

输入格式

第一行包含整数 $N$ ，表示密码的长度。

第二行输入字符串 $T$ ， $T$ 中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 $10^9 + 7$ 后的结果。

数据范围

$\le N \le 50$ ,

$\le |T| \le n$ ， $∣ T ∣$ 是 $T$ 的长度。

思路

这一题要用到基础课中的 $K MP$ 算法，最好去复习一下，链接在这，它是一个字符串匹配算法，目的是为了尽可能多的利用已知的信息进行匹配。暴力匹配的两个字符串的最坏情况是 $O (n * m)$ ，而 $K MP$ 算法可以将其降到 $O (n + m)$ 。具体来说， $K MP$ 算法的核心是 $n e x t$ 数组，其存有的信息代表着：当模式串与文本串匹配不成功时，模式串应该向右移动到什么位置，即跳过一步一步向右移动的过程。需要注意的是 $n e x t$ 数组是对模式串而言的，而不是对待匹配的文本串。

$n e x t$ 数组的具体定义是： $n e x t [i]$ 表示模式串 $P[0\cdots i - 1]$ 的最长公共前后缀的长度。

根据题意，我们需要使用 $26$ 个小写字母构造一个长度为 $n$ 的字符串 $S$ ，且 $T$ 不是字符串的子串，那么每一位密码有 $26$ 种选择，因此最坏就有 $26^n$ 种方案。

为了使构造的密码 $S$ 中不包含字符创 $T$ ，那就意味着要使匹配的过程无法到达 $T$ 的最后一位.

首先先通过 $K MP$ 处理出模式串 $T$ 的 $n e x t$ 数组，对于这道题的状态表示，使用 $f [i] [j]$ 表示已经构造了前 $i$ 位，且与模式串 $T$ 匹配到了 $j$ 位(很明显， $j$ 不能到 $m = s t r l e n (T)$ )。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N  =60, mod = 1e9 + 7;int n;
int ne[N];
char str[N];
int f[N][N];int main()
{cin >> n >> str + 1;for(int i = 2, j = 0; i <= n; i ++){while(j && str[i] != str[j + 1]) j = ne[j];if(str[i] == str[j + 1]) j ++;ne[i] = j;}f[0][0] = 1;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)for(char k = 'a'; k <= 'z'; k ++){int u = j;while(u && k != str[u + 1]) u = ne[u];if(k == str[u + 1]) u ++;f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;}int res = 0;for(int i = 0; i < m; i ++) res = (res  + f[n][i]) % mod;cout <<res << endl;return 0;
}

数据结构与算法学习笔记----动态规划·状态机模型

Acwing 1049. 大盗阿福

输入格式

输出格式

数据范围

思路

代码

Acwing 1057. 股票买卖 IV

输入格式

输出格式

数据范围

思路

代码

Acwing 1058. 股票买卖V

输入格式

输出格式

数据范围

思路

代码

Acwing 1052. 设计密码

输入格式

输出格式

数据范围

思路

代码

相关文章：