请给出dp的思路，算法复杂度应在O(n)： Bessie和Elsie正在密谋最终推翻农民约翰！他们通过N（1 ≤ N ≤ 2×10^5）条文本消息来计划。他们的对话可以用长度为N的字符串S表示，其中Si要么是B，要么是E，表示第i条消息是由Bessie或Elsie发送的。 然而，农民约翰听到了这个计划并试图拦截他们的对话。因此，S的一些字母是F，表示农民约翰混淆了消息，发送者未知。 非混淆对话的兴奋水平是奶牛双重发送的次数，即S中子串BB或EE出现的次数。您想找到原始消息的兴奋水平，但您不知道哪些是Bessie / Elsie发送的Farmer John的消息。在所有可能性上，输出S的所有可能兴奋水平。

首先考虑暴力求解，枚举S中所有可能的Bessie和Elsie发送的消息，然后对每一种情况统计BB和EE的出现次数。时间复杂度为O(2^n*n^2)，其中n为字符串长度，该算法显然会超时。

因此需要优化，考虑使用动态规划。定义dp[i][j][k]表示将前i个字符分成j个B子串和k个E子串的方案数。转移时，如果当前字符为B或E，则可以将其加入到前面的B或E子串中，也可以将其自成一个新的B或E子串。如果当前字符为F，则需要将其分别加入到B或E子串中或自成一个新的B或E子串中。最终答案即为所有dp[n][j][k]的和，其中j和k分别表示B和E的子串个数。时间复杂度为O(n^3)。

代码如下：（Python3）

相关问题

请在UVA/SPOJ/atcoder/codeforces题库中查找原题，并给出c++代码以及思路：非混淆对话的兴奋水平是奶牛双重发送的次数，即S中子串BB或EE出现的次数。您想找到原始消息的兴奋水平，但您不知道哪些是Bessie / Elsie发送的Farmer John的消息。在所有可能性上，输出S的所有可能兴奋水平。

题目链接：

UVA 12404 Excitement Levels

SPOJ EXCITE - Excitement Levels

Codeforces 583E - Watching Fireworks is Fun

题意概述：

有两只奶牛Bessie和Elsie通过一个电话线交换消息，每条消息可能是Bessie发出的、Elsie发出的，或两只奶牛都发出的。我们将Bessie和Elsie发出的消息的序列表示为两个字符串$B$和$E$，其中$B$表示Bessie发送的消息，$E$表示Elsie发送的消息。例如：当$B = \texttt{AEABBABA}$且$E = \texttt{BEABEAE}$时，下表描述了这两只奶牛之间的一些有可能的信息交换：

$$
\begin{array}{|c|c|c|}
\hline \textbf{位置} & \textbf{消息} & \textbf{发送方} \\
\hline 1 & A & B \\
\hline 2 & E & E \\
\hline 3 & A & E \\
\hline 4 & B & B \\
\hline 5 & A & E \\
\hline 6 & B & A \\
\hline 7 & A & B \\
\hline 8 & E & A \\
\hline 9 & - & - \\
\hline
\end{array}
$$

对于给定的字符串$B$和$E$，我们可以尝试恢复出她们发送的所有消息。让$S$表示任意一种可能的恢复方案中，两只奶牛发送的所有消息组成的序列。例如：上表中的恢复方案为$\texttt{AEABBAEAB}$，其中有两个BB子串和两个EE子串。我们将$S$中BB子串和EE子串的总数称为这个方案的兴奋水平。

现在，给定$B$和$E$，请你计算出所有可能的兴奋水平，并把它们按从小到大的顺序输出。

题解：

一些定义：

$B$的长度为$n$。

$E$的长度为$m$。

如果我们知道了一个恢复方案，那么我们可以在$O(n + m)$的时间内判断它的兴奋水平。具体来说，我们可以使用一个单调栈来计算所有在$S$中以BB或EE为结尾的子串的数量，其中栈中存储了在$S$中以B或E为结尾的子串的个数。

根据上面的定义，我们可以发现给定任意一个$S$，我们可以用单调栈在$O(n + m)$的时间内计算出$S$的兴奋水平，但是一个字符串有$n + m - 1$个位置，因此存在$(n + m - 1)!$多种可能的$S$。我们显然不能枚举所有的$S$。

解决方案：

我们可以直接计算出所有满足条件的$S$。具体来说，我们可以在一个递归的函数中，构建一个字符数组$S$，表示目前为止我们已经选择了哪些字符。在每个递归调用中，我们都会向$S$中添加一个字符——当前字符序列中次数较少的一个字符。如果$S$已经被填满，那么我们就可以在$O(n + m)$的时间内计算出当前方案的兴奋水平，并将其添加到答案数组中。这个递归函数的时间复杂度为$O((n + m)! (n + m))$，空间复杂度也为$O((n + m)!)$。在本题的数据范围内，这个算法可以通过本题。

代码：

Farmer John购买了三头奶头：Bessie、Elsie和Mildred，最初每头奶牛每天产出7加仑的牛奶。由于已经知道随着时间的推移奶牛的产奶量可能会发生变化，所以FJ将会在接下来的100天定期测量奶牛们的产奶量并记录下来。 记录的形式如下： 35 Bessie -2 14 Mildred +3 ... 第一个条目表示，在第35天，Bessie的产奶量比上次测量降低了2加仑 第二个条目表示，在第14天，Mildred的产奶量比上次测量增加了3加仑 Farmer John一天最多只能进行一次测量，由于FJ有点粗心大意，他的测量结果并不是按照时间顺序记下的。 为了保持奶牛们的积极性，FJ在牛棚的墙上会挂上目前产奶量最高的奶牛的照片(如果产奶量最高的奶牛有多头，那么他会挂出他们所有的照片)。 请计算出FJ需要更换墙上奶牛的照片的总天数。

首先，我们需要记录每头奶牛的当前产奶量，并在每次测量后更新它们的产奶量。我们可以使用一个字典来存储这些信息。

然后，我们可以遍历所有的测量记录，按照时间顺序更新每头奶牛的产奶量，并记录下每天产奶量最高的奶牛（或奶牛们）。

最后，我们统计有多少天产奶量最高的奶牛发生了变化，就是FJ需要更换墙上奶牛照片的总天数。

下面是Python代码实现：

from collections import defaultdict

# 初始化每头奶牛的产奶量为7
cow_milk = defaultdict(lambda: 7)

# 记录每天最高产奶量的奶牛
max_cows = set()

# 读入测量记录
n = int(input())
for i in range(n):
    day, cow, diff = input().split()
    diff = int(diff)

    # 更新奶牛的产奶量
    cow_milk[cow] += diff

    # 更新最高产奶量的奶牛
    if cow_milk[cow] > cow_milk[max_cows[0]]:
        max_cows = set([cow])
    elif cow_milk[cow] == cow_milk[max_cows[0]]:
        max_cows.add(cow)

# 统计有多少天产奶量最高的奶牛发生了变化
change_days = 0
prev_max_cows = set()
for day in range(1, 101):
    # 当前最高产奶量的奶牛
    cur_max_cows = set([cow for cow in cow_milk if cow_milk[cow] == max(cow_milk.values())])

    # 如果当前最高产奶量的奶牛与之前不同，则天数加一
    if cur_max_cows != prev_max_cows:
        change_days += 1

    prev_max_cows = cur_max_cows

print(change_days)