本期笔记的内容为状态机模型

相关链接：
1.往期笔记： 查看
2.来源：yxc老师的算法提高课

【提高版】DP知识笔记3 有猷 编

对状态机的理解：

以游戏为例：

人物站立、跑步、攻击三种状态互相转换，从而转化为抽象的数学模型，就是一种另类的状态表示方式。

状态机题面的显著特点：描述过程而非结果。

例题：

1. 大盗阿福

思路：

2. 股票买卖V

思路：
状态转移：
f[i][0] 表示对于前i天手中没货的状态。
f[i][1] 表示对于前i天手中有货，不处于冷冻期的状态。
f[i][2] 表示对于前i天手中有货，处于冷冻期的状态。

3. 设计密码

思路：
一共$m+1$个状态，每个状态26条边。
这道题比较难，蒟蒻贴一下C++代码：

#include<iostream>
#include<string>
using namespace std;
#define re register
#define Re register
#define MAXN 55
#define mod 1000000007
int n,t,go,nxt[MAXN],opt[MAXN][MAXN];
string s;
int main() {
    cin >> n >> s;
    t = s.size();s = " " + s;
    for(re int i = 2;i <= t;i++){//KMP
        while(go && s[i] != s[go + 1])go = nxt[go];
        if(s[i] == s[go + 1])go++;
        nxt[i] = go;
    }
    opt[0][0] = 1;
    for(re int i = 0;i < n;i++){
        for(re int j = 0;j < t;j++){
            for(re char k = 'a';k <= 'z';k++){
                int tmp = j;
                while(tmp && k != s[tmp + 1])tmp = nxt[tmp];
                if(k == s[tmp + 1])tmp++;
                if(tmp < t)opt[i + 1][tmp] += opt[i][j];//最重要的部分，不可以跳到终点
                opt[i + 1][tmp] %= mod;
            }
        }
    }
    int ans = 0;
    for(re int i = 0;i < t;i++){
        ans += opt[n][i];
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}