|
|
状态机模型
关于状态机是什么可以看看这个介绍：自动机 - OI Wiki
大盗阿福
题目：https://www.acwing.com/problem/content/1051/
分析：
状态机中任何一个长度是 n 的走法，都可以对应到一个抢劫方案。
f[j]表示所有走了 i 步，且当前位于状态 j 的所有走法的价值最大值。 如果当前位于状态0，说明上一次没有抢，即第 i - 1 次没有抢，位于状态1说明上一次抢了。
关于入口，入口是f[0][0] = 0，注意入口就是第一个状态，一步都没走，位于状态0，总价值也是0。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int w[N], f[N][2];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w;
f[0][0] = 0; // 一步都没走，位于状态0，总价值也是0
f[0][1] = -INF;
for (int i = 1; i <= n; i++) {
f[0] = max(f[i - 1][0], f[i - 1][1]);
f[1] = f[i - 1][0] + w;
}
cout << max(f[n][0], f[n][1]) << endl;
}
return 0;
}
股票买卖（k笔交易）
题目：1057. 股票买卖 IV - AcWing题库
分析：
这是个三维的表，在1那个二维表中只用到了上面的位置，所以从左往右覆盖或从右往左覆盖都可以。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N];
int f[M][2];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w;
// 设置初值
memset(f, 0, sizeof f);
for (int i = 0; i <= m; i++) f[1] = -INF; // 非法值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[j][0] = max(f[j][0], f[j][1] + w);
f[j][1] = max(f[j][1], f[j - 1][0] - w);
}
}
// 最后答案在状态0中找
cout << f[m][0] << endl;
return 0;
}
股票买卖（冷冻期）
题目：https://www.acwing.com/problem/content/1060/
方法一
分析：
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][3];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w;
f[0][0] = -INF, f[0][1] = -INF, f[0][2] = 0;
for (int i = 1; i <= n; i++) {
f[0] = max(f[i - 1][0], f[i - 1][2] - w);
f[1] = f[i - 1][0] + w;
f[2] = max(f[i - 1][1], f[i - 1][2]);
}
cout << max(f[n][1], f[n][2]) << endl;
return 0;
}
方法二
分析：
注意这里和方法一不同，1表示有票，0表示没票。另外这里直接写 i - 2 是不对的，可以写成max(0, i - 2)
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][3];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w;
f[0][0] = 0, f[0][1] = -INF;
for (int i = 1; i <= n; i++) {
f[0] = max(f[i - 1][0], f[i - 1][1] + w);
f[1] = max(f[i - 1][1], f[max(i - 2, 0)][0] - w);
}
cout << f[n][0] << endl;
return 0;
}
KMP自动机
题目：https://www.acwing.com/problem/content/description/1054/
分析：
https://www.cnblogs.com/icbm/p/17050519.html
AcWing 1052. 设计密码 - 糖豆爸爸 - 博客园 (cnblogs.com)
代码：时间复杂度：O(26×N^3)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n, m;
char p[N];
int f[N][N]; // 密码在第i位，模式串在第j位时的方案数
int ne[N];
int main() {
cin >> n >> p + 1;
m = strlen(p + 1);
// 构造ne数组
memset(ne, 0, sizeof ne);
for (int i = 2, j = 0; i <= n; i++) {
while (j && p != p[j + 1]) j = ne[j];
if (p == p[j + 1]) j++;
ne = j;
}
// 动态规划
f[0][0] = 1;
for (int i = 0; i < n; i++) // 密码长度是n
for (int j = 0; j < m; j++) // 不能含有的模式串长度是m（KMP自动机节点数为m）
for (char k = &#39;a&#39;; k <= &#39;z&#39;; k++) { // 每个节点的出边数
int u = j;
while (u && k != p[u + 1]) u = ne; // 状态转移
if (k == p[u + 1]) u++;
if (u < m) f[i + 1] = (f[i + 1] + f[j]) % mod; // u < m 表示不匹配
}
// 枚举模式串长度不到m的所有方案数
int res = 0;
for (int i = 0; i < m; i++) res = (res + f[n]) % mod;
cout << res << endl;
return 0;
}
代码：上面动态规划的部分，那个while循环增加了时间复杂度，所以可以预处理，用g来存状态转移图，让u能直接转移，而不是每次都搜一遍。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n, m;
char p[N];
int f[N][N]; // 密码在第i位，模式串在第j位时的方案数
int g[N][26]; // 自动机
int ne[N];
int main() {
cin >> n >> p + 1;
m = strlen(p + 1);
// 构造ne数组
memset(ne, 0, sizeof ne);
for (int i = 2, j = 0; i <= n; i++) {
while (j && p != p[j + 1]) j = ne[j];
if (p == p[j + 1]) j++;
ne = j;
}
// 预处理状态转移图
for (int j = 0; j < m; j++)
for (char k = &#39;a&#39;; k <= &#39;z&#39;; k++) {
int u = j;
while (u && k != p[u + 1]) u = ne;
if (k == p[u + 1]) u++;
g[j][k - &#39;a&#39;] = u;
}
// 动态规划
f[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (char k = &#39;a&#39;; k <= &#39;z&#39;; k++) {
int u = g[j][k - &#39;a&#39;]; // 状态转移
if (u < m) f[i + 1] = (f[i + 1] + f[j]) % mod;
}
// 枚举模式串长度不到m的所有方案数
int res = 0;
for (int i = 0; i < m; i++) res = (res + f[n]) % mod;
cout << res << endl;
return 0;
}
AC自动机
题目：https://www.acwing.com/problem/content/1055/
输入样例：
2
AAA
AAG
AAAG
2
A
TG
TGAATG
4
A
G
C
T
AGT
0
输出样例：
Case 1: 1
Case 2: 4
Case 3: -1
分析：
AC自动机（看这个） - C++从不懂到装懂 - 博客园 (cnblogs.com)
代码： |
|
发表于 2023-1-18 13:36:36
