DP状态机模型

---

大盗阿福（二态二维状态机）

题目描述：

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

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

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

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

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

输入格式：

输入的第一行是一个整数 $T$，表示一共有 $T$ 组数据。

接下来的每组数据，第一行是一个整数 $N$ ，表示一共有 $N$ 家店铺。

第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过 $1000$。

输出格式：

对于每组数据，输出一行。

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围：

$1\le T\le 50$
$1\le N\le 10^5$

输入样例：

2
3
1 8 2
4
10 7 6 14

输出样例：

8
24

代码实现

线性DP解法

import sys
from math import inf
input = sys.stdin.readline

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    nums = list(map(int, input().strip().split()))
    f = [-inf] * (n + 2)
    f[0] = f[1] = 0
    for i, x in enumerate(nums):
        f[i + 2] = max(f[i + 1], f[i] + x)
    print(f[-1])

状态机DP解法

import sys
from math import inf
input = sys.stdin.readline

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    nums = list(map(int, input().strip().split()))
    f = [[-inf] * 2 for _ in range(n + 1)]
    f[0][0] = 0
    for i, x in enumerate(nums):
        f[i + 1][1] = f[i][0] + x
        f[i + 1][0] = max(f[i][1], f[i][0])

    print(max(f[-1][1], f[-1][0]))

股票买卖 II（二态二维状态机）

题目描述：

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

输入格式：

第一行包含整数 $N$，表示数组长度。

第二行包含 $N$ 个不大于 $10000$ 的正整数，表示完整的数组。

输出格式：

输出一个整数，表示最大利润。

数据范围：

$1\le N\le 10^5$

输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

0

样例解释：
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

代码实现

import sys
from math import inf
input = sys.stdin.readline

n = int(input().strip())
price = list(map(int, input().strip().split()))

f = [[-inf] * 2 for _ in range(n + 1)]
f[0][0] = 0

for i, x in enumerate(price):
    f[i + 1][1] = max(f[i][0] - x, f[i][1])
    f[i + 1][0] = max(f[i][1] + x, f[i][0])

print(f[-1][0])

股票买卖 IV（二态三维状态机）

题目描述：

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

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

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

输入格式：

第一行包含整数 $N$ 和 $k$，表示数组的长度以及你可以完成的最大交易笔数。

第二行包含 $N$ 个不超过 $10000$ 的正整数，表示完整的数组。

输出格式：

输出一个整数，表示最大利润。

数据范围：

$1\le N\le 10^5$
$1\le k\le 100$

输入样例1：

3 2
2 4 1

输出样例1：

2

输入样例2：

6 2
3 2 6 5 0 3

输出样例2：

7

样例解释

样例1：在第1天（股票价格=2）的时候买入，在第2天（股票价格=4）的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2。

样例2： 在第2天（股票价格=2）的时候买入，在第3天（股票价格=6）的时候卖出，这笔交易所能获得利润 = 6 - 2 = 4。随后，在第5天（股票价格=0）的时候买入，在第6天（股票价格=3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3。共计利润 4 + 3 = 7。

代码实现

import sys
from math import inf
input = sys.stdin.readline

n, k = map(int, input().strip().split())
price = list(map(int, input().strip().split()))

f = [[[-inf] * 2 for _ in range(k + 1)] for _ in range(n + 1)]

for i in range(k + 1):
    f[0][i][0] = 0

for i, x in enumerate(price):
    for j in range(k + 1):
        f[i + 1][j][1] = max(f[i][j][0] - x, f[i][j][1])
        f[i + 1][j][0] = max(f[i][j][1] + x, f[i][j][0])

print(f[-1][-1][0])

股票买卖 V（三态二维状态机）

题目描述：
给定一个长度为 $N$ 的数组 $w$，数组的第 $i$ 个元素 $w_i$ 表示第 $i$ 天的股票价格。一次买入一次卖出为一笔合法交易，且不能同时产生多笔交易（必须在再次购买前出售掉之前的股票）。卖出股票后，无法在第二天买入股票（冷冻期为 $1$ 天）。设计一个方案，使得总利润最大。

输入格式：
第一行包含整数 $N$，表示数组长度。
第二行包含 $N$ 个不超过 $10000$ 的正整数，表示完整的数组。

输出格式：
输出一个整数，表示最大利润。

数据范围：
$1\le N\le 10^5$

输入样例：

5
1 2 3 0 2

输出样例：

3

样例解释：
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 $2-1=1$，第二笔交易可得利润 $2-0=2$，共得利润 $1+2=3$。

代码实现

线性与状态机混合DP

import sys
from math import inf
input = sys.stdin.readline

n = int(input().strip())
price = list(map(int, input().strip().split()))

f = [[-inf] * 3 for _ in range(n + 2)]
f[0][0] = f[1][0] = 0

for i, x in enumerate(price):
    f[i + 2][0] = max(f[i + 1][1] + x, f[i + 1][0])
    f[i + 2][1] = max(f[i][0] - x, f[i + 1][1])

print(f[-1][0])

状态机DP

import sys
from math import inf
input = sys.stdin.readline

n = int(input().strip())
price = list(map(int, input().strip().split()))

f = [[-inf] * 3 for _ in range(n + 1)]
f[0][0] = 0

# 0-空仓 1-持仓 2-冷冻期
for i, x in enumerate(price):
    f[i + 1][0] = max(f[i][0], f[i][2])
    f[i + 1][1] = max(f[i][0] - x, f[i][1])
    f[i + 1][2] = f[i][1] + x

print(max(f[-1][2], f[-1][0]))

*设计密码（KMP自动机）

题目描述：

你现在需要设计一个密码 $S$，$S$ 需要满足：

• $S$ 的长度是 $N$
• $S$ 只包含小写英文字母 $(az)$
• $S$ 不包含子串T

例如：$abc$ 和 $abcde$ 是 $abcde$ 的子串，$abd$ 不是 $abcde$ 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 $10^9+7$ 的余数。

输入格式

第一行输入整数 $N$，表示密码的长度。

第二行输入字符串 $T$，$T$ 中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 $10^9+7$ 后的结果。

数据范围

$1\le N\le 50$，$1\le |T|\le N$，$|T|$ 是 $T$ 的长度。

输入样例1：

2
a

输出样例1：

625

输入样例2：

4
cbc

输出样例2：

456924

题目分析

大佬的题解

自动机模型分析

以模式串 $ababc$ 举例

状态表示：
集合 $f[i][j]$：密码已生成 $i$ 位，并且，第 $i$ 位匹配到子串 $p$ 的位置是 $j$ 的所有方案。

属性：方案数

状态转移

$$f[i+1][j+1]+=f[i][j](j+1<m)$$

匹配失败后，根据 $KMP$ 算法去 $ne[j-1]$ 匹配对应字符。

代码实现

import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

n = int(input().strip())
p = input().strip()
m = len(p)

ne = [0] * m

idx = 0
for i in range(1, m):
    while idx and p[i] != p[idx]:
        idx = ne[idx - 1]
    if p[i] == p[idx]:
        idx += 1
    ne[i] = idx

f = [[0] * (m + 1) for _ in range(n + 1)]
f[0][0] = 1

for i in range(n):
    for j in range(min(m, i + 1)):
        for k in range(ord('a'), ord('z') + 1):
            ch, u = chr(k), j
            while u and ch != p[u]:
                u = ne[u - 1]
            if ch == p[u]:
                u += 1
            f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD

print(sum(f[-1][:m]))