大盗阿福

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

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

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

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

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

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

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

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

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

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

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

数据范围
1 ≤ T ≤ 50,
1 ≤ N ≤ 105

输入样例：

1
2
3
4
5
6
2
3
1 8 2
4
10 7 6 14

输出样例：

1
2
3
8
24

样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。

对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

思路1：
我们可以定义一个数组，为f[]。

f[i] 表示抢劫前 i 家能得到的最多现金数量。

那么我们前ii家的抢劫结果就有两种情况：

第一种情况：不偷第 i 家店铺
那么f[i]=f[i−1]
第二种情况：偷第ii家店铺
那么f[i]=f[i−1]+w[i]
(w[i] 表示第ii家店铺总共的现金)

思路1出现的问题：
如果第i−1 家店已经被抢了，那么如果抢了第 i 家，那是不符合题目要求的。

那怎么办呢？

正确方法(思路2)：
我们把f数组定为二维的，即f[][]
我们用数组储存两种情况：偷与不偷。

f[i][0] 代表的是不偷第ii家店铺能得到的最多现金数量；
f[i][1] 代表的是偷第ii家店铺能得到的最多现金数量。

则就会出现三种情况：状态机：

解释：

图中红色的线是可行方案，你可以不抢第i−1家，也不抢第 i 家；
你可以不抢第i−1家，但抢第 i 家。
你可以抢第i−1家，但不抢第 i 家；

那么我们就可以得出状态转移方程了：

1
2
3
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N], f[N][2];
int main()
{
	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]) << endl;
	}	
	return 0;
} 

笔记学习：
作者：linmujin
链接：https://www.acwing.com/solution/content/23723/
来源：AcWing

股票买卖 IV

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

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

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

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

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

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

数据范围
1 ≤ N ≤ 105,
1 ≤ k ≤ 100

输入样例1：

1
2
3
3 2
2 4 1

输出样例1：

1
2
2

输入样例2：

1
2
3
6 2
3 2 6 5 0 3

输出样例2：

1
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.

股票状态机：



初始化：

1. 如果一种状态不合法，或者不希望从这个状态转移过来 ，那么就把它设成正无穷或负无穷
   因为这个题要求最大值，所以把不合法的设成负无穷，也这样这个状态不可能用来更新后来的状态
   例如这道题中f[i][0][1]表示，如果我们处理了0笔股票，并且我们手中居然还有票，这显然是不可能的。还有不合法情况，例如：f[0][j][1]等。
2. 如果我们处理了0笔股票并且目前手里没有票，那收入就是0，即f[i][0][0] = 0

所以我们将f先全置成负无穷，再单独处理为0的情况

状态转移方程：
定义一次买卖为完整的交易，所以当买入的时候为第ii次交易，随后卖出也算作是第 i 次交易，而下一次的买入算作i+1次交易,下一次的卖出算作i+1次交易，如果你把卖出算作是新的第 i 次交易，那么对于你的上一次买入便是 i−1次交易，因为对于第一次交易而言有买入才有卖出，当i=1的时候买入算作是第0次买卖，显然是不对的。

注意：
这里状态机的过程，对于每个股票，要么就买，要么就卖，不能说是买了然后在同一个点直接卖掉，这样是不符合状态机模型的，因此对于上述转移方程可以会有人提出疑问。
为什么状态转移方程不能是下面代码，即卖的时候才算做了一次交易，原代码是买的时候才算一次交易

1
2
3
f[i][j][0] = max(f[i - 1][j - 1][1] + w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][0] - w[i], f[i - 1][j][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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 110;
const int INF = 0x3f3f3f3f;
int n, k;
int a[N], f[N][M][2]; // 前i天，正在进行第j次交易，交易状态 
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	// 初始化 
	memset(f, -0x3f, sizeof f); // 前i天进行0次交易且手里有货的值为负无穷 
	for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0; // 前i天进行0次交易且手里无货的值为0 
	
	for (int i = 1; i <= n; i ++ ) 
		for (int j = 1; j <= k; j ++ ) {
			// 一次完整的交易：买入到卖出（0->1->0） 
			f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);
			f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - a[i]);
		}
	int res = 0;
	for (int i = 1; i <= k; i ++ ) res = max(res, f[n][i][0]);
	cout << res;
	return 0;
}

股票买卖 V

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

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

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

输入格式
第一行包含整数 N，表示数组长度。

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

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

数据范围
1 ≤ N ≤ 10⁵

输入样例：
5
1 2 3 0 2

输出样例：
3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][3];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> w[i];
	// 初始化 
	f[0][2] = 0;
	f[0][0] = f[0][0] = -INF;
	
	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]);
 	} 
	cout << max(f[n][1], f[n][2]);
	return 0;
}

设计密码

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

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

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

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

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

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

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

输出格式
输出一个正整数，表示总方案数模 10⁹+7 后的结果。

数据范围
1 ≤ N ≤ 50,
1 ≤ |T| ≤ N，|T|是T的长度。

输入样例1：

1
2
3
2
a

输出样例1：

1
2
625

输入样例2：

1
2
3
4
cbc

输出样例2：

1
2
456924

没懂

状态机

动态规划

为什么这样的状态表示是可行的呢?
因为S数组中的第n位有26个小写字母,匹配在T中的位置一定存在(因为不匹配,匹配到的位置是0),
所以把所有f[n][0~m-1]加起来即为总方案数

首先怎么确定状态，这里把 f[i][j] 表示为对于现在生成的密码已经到了第 i 个了，并且当前在子串中的位置 是 j 的密码个数。

一个状态机问题，先要明确有几种状态，对于每一个固定的i 和 j 来说，总共有26种状态，对于26个字母。

如何判断某一种方案是可能的呢？联系KMP的子串匹配方法，就是判断对于固定的 i 和 j 判断当前字符是不是和子串中 j+1 的字符匹配，匹配就j++，不匹配 j 就回跳，如果我们到最后，也就是 i = 26 的时候都没办法使 j 到子串的末尾，那么就意味着我们的密码中没有子串，也就是一种可能。

根据上面的分析，我们再来看这个状态的定义，想一想状态方程，因为每一个字母都对于固定的 i 和 j 都有固定的判断结果，那么我们只要对于每一种 i 和 j枚举一下26个字母 ，根据上面的判断方法判断一下是否可能 如果可能就可以状态转移了

1：KMP的预处理，初始化next数组，代码中用ne表示

2：循环：
2.1：第一层循环：枚举一下i的位置，也就是当前密码的长度（代码中是从0开始的）
2.2：第二层循环：枚举一下j 的位置，也就是再子串中的位置
2.3：第三层循环：枚举一下 所有的字母 ，并且应KMP判断是否当前密码有子串，如果没有更新f[i+1][j]，为什么是i+1，而不是 i 呢？因为这里定义的状态是已经有的长度，不包括当前枚举的字母，我当时也迷惑了一会，现在写出来帮助一下不懂的小伙伴

3：最后把所有可能的 j 的位置加起来，就是答案，因为i最后肯定是 n ，所以枚举一下未知的 j 。
KMP中还有一个细节，就是要用u来对每一种状态更新，不要用j，不要搞错了，j是枚举的状态，如果用 j 的话更新的状态就不对了，注意一下哈。

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 = 55, mod = 1e9 + 7;
int f[N][N]; // 已经生成了i位，且第i位匹配到字符串中的位置j的方案数 
int ne[N];
char str[N];
int main()
{
	int n, m;
	cin >> n >> str + 1;
	m = strlen(str + 1);
	for (int i = 2, j = 0; i <= m; i ++ ) {
		while (j && str[j + 1] != str[i]) j = ne[i];
		if (str[j + 1] == str[i]) j ++ ;
		ne[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 && str[u + 1] != k) u = ne[u];
				if (str[u + 1] == k) 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;
	return 0;
}

修复DNA

生物学家终于发明了修复DNA的技术，能够将包含各种遗传疾病的DNA片段进行修复。

为了简单起见，DNA看作是一个由’A’, ‘G’ , ‘C’ , ‘T’构成的字符串。

修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。

例如，我们可以通过改变两个字符，将DNA片段”AAGCAG”变为”AGGCAC”，从而使得DNA片段中不再包含致病片段”AAG”，”AGC”，”CAG”，以达到修复该DNA片段的目的。

需注意，被修复的DNA片段中，仍然只能包含字符’A’, ‘G’ , ‘C’ , ‘T’。

请你帮助生物学家修复给定的DNA片段，并且修复过程中改变的字符数量要尽可能的少。

输入格式
输入包含多组测试数据。

每组数据第一行包含整数N，表示致病DNA片段的数量。

接下来N行，每行包含一个长度不超过20的非空字符串，字符串中仅包含字符’A’, ‘G’ , ‘C’ , ‘T’，用以表示致病DNA片段。

再一行，包含一个长度不超过1000的非空字符串，字符串中仅包含字符’A’, ‘G’ , ‘C’ , ‘T’，用以表示待修复DNA片段。

最后一组测试数据后面跟一行，包含一个0，表示输入结束。

输出格式
每组数据输出一个结果，每个结果占一行。

输入形如”Case x: y”，其中x为测试数据编号（从1开始），y为修复过程中所需改变的字符数量的最小值，如果无法修复给定DNA片段，则y为”-1”。

数据范围
1 ≤ N ≤ 50

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
AAA
AAG
AAAG    
2
A
TG
TGAATG
4
A
G
C
T
AGT
0

输出样例：

1
2
3
4
Case 1: 1
Case 2: 4
Case 3: -1

太难了啊

AC自动机其实是一个状态转移，该机器可以根据输入自动改变内部状态，并输出最终状态。
AC自动机的状态转移可以看成是一个拓扑图，一个简单的状态转移如下图所示：

start表示起始状态，end表示出口状态，其余1、2、3都表示机器可以到达的状态。

例如输入为cacabac，状态转移如下：

• 起始状态为start，第一个字符为c，因此第一步停在原地start
• 第二个字符为a，这回可以前进了，到达状态1
• 第三个字符为c，跳回状态0(start)
• 第四个字符为a，转移到1
• 第五个字符为b，转移到2
• 第六个字符为c，转移到2
• 第七个字符为c，转移到3，并自动到达出口end

特别地，了解KMP原理的同学可以发现，如果abc表示模式字符串，则到达出口end表示一个字符串匹配成功。

那么这和AC自动机有啥关系呢？上面不就是个简单的状态转移图吗？是的，AC自动机其实并没有新的内容，只是我们看待问题的眼光不同了。

如果将构建状态转移图的过程看成，制造一台AC自动机，一旦AC自动机生成，模式匹配问题可以看成向这台机器进行输入，然后机器内部状态自动进行改变，最后输出最终状态。

这个过程形象化的如下图所示：

还可以知道，1、由于输入字符串长度和内部状态有限，因此机器一定会停机。2、一台AC自动机只能处理同一类模式匹配问题，因此我们可以构建多台机器，根据问题的不同交给相应的机器。

以修复DNA为例。

由题意可知，先建立字典树，将每个单词结尾进行标记，表示该点为致病片段不可达。

接下来构建AC自动机，构建的目的是根据next数组的定义，如果一个单词的后缀是致病片段，那么该点也要被标记，这样标记出所有非法节点。

原题要求最少的改动可以不包含致病片段，就是从树根出发，每一步可以选择ATCG中的任何一个。

如果第k步选择的字符和DNA片段的相同，说明这一步没有修改，代价为0，反之为1。

一共走m=len(DNA)步，前提是不能走到被标记的节点，这样所有走法中的最小代价。

采用DP即可，状态转移方程如下：

1
2
3
if (!st[trie[u][i]])
    res = min(res, dp(trie[u][i], len + 1) + (id[s[len]] == i ? 0 : 1));

表示下一步必须选择没被标记的点转移，代价为0或1取决于这一步选择的字符。

dp(u,v)表示从节点u出发，当前走到第v步，到终点所有走法的最小代价。终点的含义为走了m步，且没有经过标记点的一种走法。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int tr[N][4], dar[N], idx;
int q[N], ne[N];
char str[N];
int f[N][N];
int get(char c)
{
	if (c == 'A') return 0;
	if (c == 'T') return 1;
	if (c == 'G') return 2;
	return 3;
}
void insert()
{
	int p = 0;
	for (int i = 0; str[i]; i ++ ) {
		int t = get(str[i]);
		if (tr[p][t] == 0) tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	dar[p] = 1;
}
void build()
{
	int hh = 0, tt = -1;
	for (int i = 0; i < 4; i ++ ) 
		if (tr[0][i])
			q[ ++ tt] = tr[0][i];
	while (hh <= tt) {
		int t = q[hh ++ ];
		for (int i = 0; i < 4; i ++ ) {
			int p = tr[t][i];
			if (!p) tr[t][i] = tr[ne[t]][i];
			else {
				ne[p] = tr[ne[t]][i];
				q[ ++ tt] = p;
				dar[p] |= dar[ne[p]];
			}
		}
	}
}
int main()
{
	int T = 1;
	while (scanf("%d", &n), n) {
		memset(tr, 0, sizeof tr);
		memset(dar, 0, sizeof dar);
		memset(ne, 0, sizeof ne);
		idx = 0;
		for (int i = 0; i < n; i ++ ) {
			cin >> str;
			insert();
		}
		build();
		cin >> str + 1;
		m = strlen(str + 1);
		memset(f, 0x3f, sizeof f);
		f[0][0] = 0;
		for (int i = 0; i < m; i ++ ) 
			for(int j = 0; j <= idx; j ++ )
				for (int k = 0; k < 4; k ++ ) {
					int t = get(str[i + 1]) != k;
					int p = tr[j][k];
					if (!dar[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
				}
		int res = 0x3f3f3f3f;
		for (int i = 0; i <= idx; i ++ ) res = min(res, f[m][i]);
		if (res == 0x3f3f3f3f) res = -1;
		cout << "Case " << T ++ << ": " << res << endl;
	}
	return 0;
} 

笔记学习：
作者：yuanwen
链接：https://www.acwing.com/solution/content/24795/
来源：AcWing

最后

以上就是自觉心锁最近收集整理的关于状态机模型大盗阿福股票买卖 IV股票买卖 V设计密码修复DNA的全部内容，更多相关状态机模型大盗阿福股票买卖内容请搜索靠谱客的其他文章。