1.4 状态机模型

大盗阿福

状态表示：f[i][k]，其中k=0/1。

集合：抢劫前i家店，并且当前状态是k（0不偷，1偷）的所有抢劫方案。

属性：max

状态计算：

f[i][1]=f[i-1][0]+a[i]

f[i][0]=max(f[i-1][0],f[i-1][1])

答案： max(f[n][0],f[n][1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N][2];
int main ()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        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];
        }
        cout << max (f[n][0],f[n][1]) << '\n';
    }
    return 0;
}

滚动数组优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[2][2];
int main () 
{
    int T;
    cin >> T;
    while (T--) 
    {
        cin >> n;
        for (int i = 1;i <= n;i++)
            cin >> a[i];
        memset (f,0,sizeof (f));
        for (int i = 1;i <= n;i++) 
        {
            f[i & 1][0] = max (f[(i - 1) & 1][0],f[(i - 1) & 1][1]);
            f[i & 1][1] = f[(i - 1) & 1][0] + a[i];
        }
        cout << max (f[n & 1][0],f[n & 1][1]) << '\n';
    }
    return 0;
}

从转移去优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N];
int main ()
{
    int T;
    cin >> T;
    while (T--) 
    {
        cin >> n;
        for (int i = 1;i <= n;i++) 
            cin >> a[i];
        f[1] = a[1];
        for (int i = 2;i <= n;i++) 
            f[i] = max (f[i - 1],f[i - 2] + a[i]);
        cout << f[n] << '\n';
    }
    return 0;
}

股票买卖 \(\textrm{IV}\)

状态分析：f[i][j][k],k=0/1.，表示目前第i天，已经完成j笔交易并且k=0表示当前未持有股票，k=1表示当前持有股票。

状态转移看题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010,K = 110;
int n,k;
int a[N];
int f[N][K][2];
int main () {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) 
        cin >> a[i];
    memset (f,-0x3f,sizeof (f));
    f[0][0][0] = 0;
    for (int i = 1;i <= n;i++) 
    {
        for (int j = 0;j <= k;j++) 
        {
            f[i][j][0] = f[i - 1][j][0];
            //直接转移，今天没有可能前一天就是没有
            if (j) 
                f[i][j][0] = max (f[i][j][0],f[i - 1][j - 1][1] + a[i]);
            //也可能是卖出去了
            f[i][j][1] = max (f[i - 1][j][1],f[i - 1][j][0] - a[i]);
            //可能是原来就有，可能是买进来了。
        }
    }
    int ans = 0;
    for (int i = 0;i <= k;i++) 
        ans = max (ans,f[n][i][0]);
    cout << ans << '\n';
    return 0;
}

股票买卖 \(\textrm{V}\)

添加一个冷冻期状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N][3];
int main ()
{
    cin >> n;
    for (int i = 1;i <= n;i++) 
        cin >> a[i];
    memset (f,-0x3f,sizeof (f));
    f[0][0] = 0;
    for (int i = 1;i <= n;i++) 
    {
        f[i][0] = max (f[i - 1][0],f[i - 1][2]);
        //未持有可能前一天就是未持有，也可能就是刚过冷冻期
        f[i][1] = max (f[i - 1][1],f[i - 1][0] - a[i]);
        //持有可能前一天就是持有，也可能就是刚刚买进来
        f[i][2] = f[i - 1][1] + a[i];
        //冷冻期一定就是买过的加上价钱
    }
    cout << max (f[n][0],f[n][2]) << '\n';
//持有股票一定就是未持有的
    return 0;
}

设计密码

QQ浏览器截图20210101073445.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n, m;
char s[N];
int f[N][N], ne[N];
int main()
{
    cin >> n >> s + 1;
    m = strlen(s + 1);
    //KMP预处理前缀表
    for (int i = 2, j = 0; i <= m; ++ i)
    {
        while (j && s[i] != s[j + 1]) j = ne[j];
        if (s[i] == s[j + 1]) ++ j;
        ne[i] = j;
    }
    //DP
    f[0][0] = 1;
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < m; ++ j)
        {
            for (char ch = 'a'; ch <= 'z'; ++ ch)   //枚举第i+1个字符
            {
                int ptr = j;    //计算枚举到第i+1个字符后，后缀匹配的最大长度
                while (ptr && s[ptr + 1] != ch) ptr = ne[ptr];
                if (s[ptr + 1] == ch) ++ ptr;
                f[i + 1][ptr] = (f[i + 1][ptr] + f[i][j]) % mod;    //更新i+1的状态
            }
        }
    }
    //统计所有目标状态
    int res = 0;
    for (int j = 0; j < m; ++ j) res = (res + f[n][j]) % mod;
    cout << res << '\n';
    return 0;
}