跳转至

状态机模型

另类的状态表示方式:

  • 状态机: “过程” 而非 “结果”
  • 状态压缩DP

"状态机模型"和"01背包问题"的区别:

  • 01背包中每个物品选或不选都是独立的， 不受前者约束不对后者产生影响，
  • 状态机不一样。

换成01那种状态之间的转化图来看的话, 01背包中0和1的转化不受任何约束，可以说是有向完全图；但是状态机不一样，由于某些条件下的边不存在，于是我们 在计算本次状态之前可能需要了解前一次的状态 ，于是需要状态细分标记

1049 大盗阿福

2 状态自动机

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

思路1: 动态规划

f[i]: 前 i 家的最大收益

思路2: 状态机

C++
 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
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e5+10, INF = 0x3f3f3f3f;

int T;
int n;
int a[maxn];
int f[maxn][2];

void theft_func()
{
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][1], f[i - 1][0]);
        f[i][1] = f[i - 1][0] + a[i];
    }
    cout << max(f[n][0], f[n][1]) << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    // 初始化 (非常重要)
    // f[0][0]: 没店铺, 也不取, 合理, 0
    // f[0][1]: 没店铺, 却取了, 非法, 安排一个"不可能"的值
    f[0][0] = 0;
    f[0][1] = -INF;

    while (T--)
    {
        cin >> n;
        for (int i=1; i<=n; i++) cin >> a[i];
        theft_func();
    }

    return 0;
}
}

1057 股票买卖 IV

2 状态自动机

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

状态机

根据题目中的定义: “手中无货”才表示事先经历了完整的交易

  • 状态表示 f[i,j,0] AND f[i,j,1]
    • 集合: 前 \(i\) 天 进行了 \(j\) 场交易, 且当前手中 无货(0) / 有货(1)
    • 属性: max
  • 状态计算
    • f[i, j, 0] = max(f[i-1, j, 0], f[i-1, j, 1] + w[i])
    • f[i, j, 1] = max(f[i-1, j, 1], f[i-1, j-1, 0] - w[i])
    • 注意: \(j-1\) 和 \(j\) 的区别, 这和题目中 "一次买入卖出合为一笔交易" 相关
C++
 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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, k;
int w[N];
int f[N][M][2];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0; //初始状态f[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] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - w[i]);
        }
    }

    int res = 0;
    for (int j = 0; j <= k; ++ j) res = max(res, f[n][j][0]); 
    // 目标状态f[n][j][0], 表示 "手中无货" (经历了完整的交易数)

    cout << res << endl;

    return 0;
}

思考: 如何初始化?

  • 初始可能值: 赋为0
  • 初始不可能值: 赋为 INF or -INF
    • 题目要求max, 则赋为 -INF
    • 反之, 赋为 INF

1058 股票交易 V

3 状态自动机

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)

初始化:

  1. f[0][2] = 0: 在交易开始前（第0天），你手中没有股票，并且不处于冷冻期
  2. f[0][0] = -INF: 在交易开始前（第0天），你的手中就已经持有一支股票
  3. f[0][1] = -INF: 在交易开始前（第0天），你手中没有股票，但你正处于冷冻期
C++
 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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int w[N];
int f[N][3];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    // --- 初始化
    memset(f, -0x3f, sizeof f);
    f[0][2] = 0;
    // ---

    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][2], f[i - 1][1]);
    }

    printf("%d\n", max(f[n][1], f[n][2]));

    return 0;
}