Loading... 提前祝愿各位 **开学快乐** ## 概念 每次都会产生很多不同的动作(状态) 跑步可以转换成站立.... 站立可以转换成走路... 两两之间都有一种转化的方式 那就可以将每个动作设为点、两两转化的过程设为边。 一系列**有序**的序列。 状态机可以将其描述清楚。 这个过程就叫做状态机模型 与普通 $dp$ 问题的区别是、多出了一个状态。 ## 大盗阿福 [题目链接](https://www.acwing.com/problem/content/1051/) ### 题目解析 相邻 $>=2$ 时才不会触发警报。问不触发警报情况下最大的选择数。即、两两之间差 $1$ 、最大选择多少。 ### 分析 那么对于每个 $f[i]$ 则会有 $f[i] = max(f[i - 2] + w[i], f[i - 1])$ 这是背包解法。我们可以通过状态机进行分解。 那么我们可以设定两个状态 $0$、$1$ 分别表示未选择最后一个店铺、以及选最后一个商店。 我们发现 $0$ 可以跳到 $0$ 或者 $1$ $1$ 只能跳到 $0$ 那么我们可以开 $f[i][j]$ 表示第 $i$ 个数、状态为 $j$ 时的最优结果 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-ec49640a1ab732363d5abf5ae0bf3d8548" aria-expanded="true"><div class="accordion-toggle"><span>Code</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-ec49640a1ab732363d5abf5ae0bf3d8548" class="collapse collapse-content"><p></p> ```cpp #include <iostream> using namespace std; const int N = 1e5 + 5, INF = 2e9; int a[N], f[N][2]; int main() { int t; scanf("%d", &t); while (t -- ) { int n; scanf("%d", &n); for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); } f[0][0] = 0; f[0][1] = -INF; 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] + a[i]; } printf("%d\n", max(f[n][1], f[n][0])); } return 0; } ``` <p></p></div></div></div> ## 股票买卖 IV [题目链接](https://www.acwing.com/problem/content/1059/) ### 分析 都会存在两种状态、分别为、有货或者没货。有货需要 $w[i]$ 卖出或者不买、没货可以不买或者 $-w[i]$ 买入。 限制了最多购买了 $k$ 次、那么我们再加一维即可。 $f[i][j][k]$ 表示 前 $i$ 物品 进行 $j$ 次操作 $k$ 表示当前的状态。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-4b2254a1ab57d66293ff12eb0df03f8735" aria-expanded="true"><div class="accordion-toggle"><span>Code</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-4b2254a1ab57d66293ff12eb0df03f8735" class="collapse collapse-content"><p></p> ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 1e5 + 5, K = 1e2 + 5, INF = 2e9; int a[N], f[N][K][2]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); } memset(f, -127, 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] + a[i]); f[i][j][1] = max(f[i - 1][j - 1][0] - a[i], f[i - 1][j][1]); } } int res = 0; for (int i = 1; i <= m; i ++ ) { res = max(res, f[n][i][0]); } printf("%d", res); return 0; } ``` <p></p></div></div></div> ## 股票买卖 V 股票带师 (确信) [题目链接](https://www.acwing.com/problem/content/1060/) ### 题目解析 与上题、唯一的区别是、加入了冷冻期。即卖出后、需等待一天 ### 分析 每个 手中有货的状态。由手中无货的 $i - 1$ 天以及 手中无货的 $>= 2$ 天 那么我们可以画出  那么、我们可以进一步推出转移方程。 那么我没就有三个状态了。 $0$ 代表 有货 $1$ 代表 冷却期 $2$ 代表过了冷却期。 $1、2$ 共同标识无货 以下为本题的转移方程。 $f[i][0] = max(f[i - 1][0], f[i - 1][2] - a[i])$ $f[i][1] = f[i - 1][0] + a[i]$ $f[i][2] = max(f[i - 1][1], f[i - 1][2])$ 那么我们就不难写出本题代码。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-f420eff5b3b937a0ec35765cace77a4892" aria-expanded="true"><div class="accordion-toggle"><span>Code</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-f420eff5b3b937a0ec35765cace77a4892" class="collapse collapse-content"><p></p> ```cpp #include <iostream> #include <cstdio> using namespace std; const int N = 1e5 + 5, INF = 2e9; int a[N], f[N][3], n; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); } f[0][0] = -INF; f[0][1] = -INF; for (int i = 1; i <= n; i ++ ) { f[i][0] = max(f[i - 1][0], f[i - 1][2] - a[i]); f[i][1] = f[i - 1][0] + a[i]; f[i][2] = max(f[i - 1][1], f[i - 1][2]); } printf("%d", max(f[n][0], max(f[n][1], f[n][2]))); return 0; } ``` <p></p></div></div></div> ## 设计密码 [题目链接](https://www.acwing.com/problem/content/1054/) ### 题目解析 第一眼看、根本没和状态机合在一起 /kk 有多少个三角形 实际、题意有样例可以理解。 ### 分析 $kmp + 状态机$ 首先、我们发现。字符串我们可以堪称一条路。不能走到终点。但是可以在这条路上走任何的位置。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-7a2deed3d97f41a3381af27a1a53678131" aria-expanded="true"><div class="accordion-toggle"><span>Code</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-7a2deed3d97f41a3381af27a1a53678131" class="collapse collapse-content"><p></p> ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 50 + 5, mod = 1e9 + 7; int f[N][N], nxt[N], n; char str[N]; int main() { cin >> n >> str + 1; int m = strlen(str + 1); int j = 0; for (int i = 2; i <= n; i ++ ) { while (j && str[i] != str[j + 1]) j = nxt[j]; if (str[i] == str[j + 1]) j ++; nxt[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 && str[u + 1] != k) u = nxt[u]; if (str[u + 1] == k) u ++; if (u < m) 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; } printf("%d", res); return 0; } ``` <p></p></div></div></div> That`s all. 最后修改:2020 年 08 月 21 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 End.