状态机模型

博主： smallfang
发布时间：2020 年 08 月 18 日
414 次浏览
暂无评论
862字数
分类：算法笔记

提前祝愿各位 **开学快乐**

## 概念

每次都会产生很多不同的动作（状态）

跑步可以转换成站立....
站立可以转换成走路...

两两之间都有一种转化的方式

那就可以将每个动作设为点、两两转化的过程设为边。

一系列**有序**的序列。

状态机可以将其描述清楚。

这个过程就叫做状态机模型

与普通 $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$ 时的最优结果

```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;
}
```

## 股票买卖 IV

[题目链接](https://www.acwing.com/problem/content/1059/)

### 分析

都会存在两种状态、分别为、有货或者没货。有货需要 $w[i]$ 卖出或者不买、没货可以不买或者 $-w[i]$ 买入。

限制了最多购买了 $k$ 次、那么我们再加一维即可。

$f[i][j][k]$ 表示 前 $i$ 物品 进行 $j$ 次操作 $k$ 表示当前的状态。

```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;
}
```

## 股票买卖 V

股票带师 （确信）

[题目链接](https://www.acwing.com/problem/content/1060/)

### 题目解析

与上题、唯一的区别是、加入了冷冻期。即卖出后、需等待一天

### 分析

每个 手中有货的状态。由手中无货的 $i - 1$ 天以及 手中无货的 $>= 2$ 天

那么我们可以画出
![image.png](https://blog.smallfang.fun/usr/uploads/2020/08/3537668360.png)

那么、我们可以进一步推出转移方程。

那么我没就有三个状态了。 $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])$

那么我们就不难写出本题代码。

```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;
}
```

## 设计密码

[题目链接](https://www.acwing.com/problem/content/1054/)

### 题目解析

第一眼看、根本没和状态机合在一起 /kk

有多少个三角形

实际、题意有样例可以理解。

### 分析

$kmp + 状态机$

首先、我们发现。字符串我们可以堪称一条路。不能走到终点。但是可以在这条路上走任何的位置。

```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;
}
```

That`s all.

最后修改：2020 年 08 月 21 日

End.

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

2020日记（原CSP日记）
评论数： 11
入境教育游记
评论数： 5
博客三周年祭
评论数： 5
数学函数学习笔记
评论数： 4
友善题解 #1 选择客栈
评论数： 4

hotbeautysoup
|´・ω・)ノ加油啊
WyyOIer
祝贺
WyyOIer
前排支持
WyyOIer
尝试回复
WyyOIer
悲

A*算法笔记
评论数： 0
高精度计算
评论数： 0
中考日记
评论数： 2
集训日记
评论数： 0
友善题解 #2 复制书稿
评论数： 0

状态机模型

smallfang • 2020 年 08 月 18 日

提前祝愿各位 **开学快乐**

## 概念

每次都会产生很多不同的动作（状态）

跑步可以转换成站立....
站立可以转换成走路...

两两之间都有一种转化的方式

那就可以将每个动作设为点、两两转化的过程设为边。

一系列**有序**的序列。

状态机可以将其描述清楚。

这个过程就叫做状态机模型

与普通 $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$ 时的最优结果

```cpp
#include <iostream>

using namespace std;

const int N = 1e5 + 5, INF = 2e9;

int a[N], f[N][2];

## 股票买卖 IV

[题目链接](https://www.acwing.com/problem/content/1059/)

### 分析

都会存在两种状态、分别为、有货或者没货。有货需要 $w[i]$ 卖出或者不买、没货可以不买或者 $-w[i]$ 买入。

限制了最多购买了 $k$ 次、那么我们再加一维即可。

$f[i][j][k]$ 表示 前 $i$ 物品 进行 $j$ 次操作 $k$ 表示当前的状态。

```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];

## 股票买卖 V

股票带师 （确信）

[题目链接](https://www.acwing.com/problem/content/1060/)

### 题目解析

与上题、唯一的区别是、加入了冷冻期。即卖出后、需等待一天

### 分析

每个 手中有货的状态。由手中无货的 $i - 1$ 天以及 手中无货的 $>= 2$ 天

那么我们可以画出
![image.png](https://blog.smallfang.fun/usr/uploads/2020/08/3537668360.png)

那么、我们可以进一步推出转移方程。

那么我没就有三个状态了。 $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])$

那么我们就不难写出本题代码。

```cpp
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 5, INF = 2e9;

int a[N], f[N][3], n;

## 设计密码

[题目链接](https://www.acwing.com/problem/content/1054/)

### 题目解析

第一眼看、根本没和状态机合在一起 /kk

有多少个三角形

实际、题意有样例可以理解。

### 分析

$kmp + 状态机$

首先、我们发现。字符串我们可以堪称一条路。不能走到终点。但是可以在这条路上走任何的位置。

```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];

That`s all.

发表评论 取消回复

状态机模型

发表评论取消回复