状态机

状态机

解析

状态机按现在的认识，可以看做一种观察问题的思路
将不同的状态看做“点”，状态之前可以转化的情况看做“边”
由此某个问题就可以变成由点和边组成的“过程”
然后根据过程来编写代码，在某些问题的理解上会更加清晰

练习

1049. 大盗阿福

思路

将选第i家店铺作为状态1，不选作为状态0。
由此，根据题目，就可以有三条边：
1.0 -> 0
2.0 -> 1
3.1 -> 0

然后将f[i]设为前i个店铺可以获取的最大价值即可

#include <iostream>
using namespace std;

const int N = 100010;
int f[N][2];

int main() {
    int T;
    cin >> T;
    while (T --) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++) {
            int v;
            cin >> v;
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + v;
        }
        
        cout << max(f[n][1], f[n][0]) << endl;
    }
    
    return 0;
}

1057. 股票买卖 IV

思路

将题目所给状态表示为：当前手上有股票，当前手上没股票
设有为1，没有为0
状态表示为：
1.1 -> 1
2.1 -> 0
3.0 -> 0
4.0 -> 1

状态表示为：在前i天，交易进行j笔时的最大利润

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
const int N = 100010, M = 110;
int f[N][M][2];

int main() {
    cin >> n >> m;
    memset(f, -0x3f, sizeof f);                          //将所有状态设置为不可达
    for (int i = 0; i <= n; i ++) f[i][0][0] = 0;        //第i天，不进行交易的利润都为0
    for (int i = 1; i <= n; i ++) {
        int v;
        cin >> v;
        for (int j = 1; j <= m; j ++) {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + v);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - v);
        }
    }
    
    int res = 0;
    for (int i = 0; i <= m; i ++) res = max(res, f[n][i][0]);
    cout << res << endl;
    
    return 0;
}

1058. 股票买卖 V

思路

加入了冷冻期这个状态
设有股票为0， 没有股票第一天为1，没有股票第二天为2
则有：
1.0 -> 0
2.0 -> 1
3.1 -> 2
4.2 -> 2
5.2 -> 0

入口在没有股票的第二天，这样可以保证立刻就可以买股票，转化为0的状态
出口在没有股票的第一天和第二天，取最大值即可

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

int f[N][3];

int main() {
    int n;
    cin >> n;
    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i ++) f[i][2] = 0;
    for (int i = 1; i <= n; i ++) {
        int v;
        cin >> v;
        f[i][0] = max(f[i - 1][2] - v, f[i - 1][0]);
        f[i][1] = f[i - 1][0] + v;
        f[i][2] = max(f[i - 1][2], f[i - 1][1]);
    }
    
    cout << max(f[n][1], f[n][2]) <<  endl;
    
    return 0;
}

1052. 设计密码

思路

kmp + dp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, mod = 1e9 + 7;
int f[N][N];
char str[N];
int n;

int main() {
    cin >> n;
    cin >> str + 1;
    int m = strlen(str + 1);
    
    int next[N] = {0};
    
    for (int i = 2, j = 0; i <= m; i ++) {
        while (j && str[i] != str[j + 1]) j = next[j];
        if (str[i] == str[j + 1]) j ++;
        next[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 = next[u];
                if (k == str[u + 1]) 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;
    cout << res << endl;
    
    return 0;
}