请给出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的所有可能兴奋水平。

时间: 2023-05-24 18:06:37 浏览: 257

首先考虑暴力求解，枚举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）

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代码实现： ```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) ```

请在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)!)$。在本题的数据范围内，这个算法可以通过本题。代码：

阅读全文

相关推荐

编程语言基于C++的紫藤花食用算法优化：解决时间超限问题及奶牛进食路径规划

P2666 [USACO07OCT] Bessie's Secret Pasture S

bessie_come_home.rar_Home Home

正在使用一堆共 K 张（N≤K≤100,000; K 是 N 的倍数）纸牌与 N−1 个（2≤N≤100）朋友玩取牌游戏。纸牌中共包含 M=K/N 张 “good” 牌和 K−M 张 “bad” 牌。 Bessie 负责发牌，她当然想独占所有 “good” 牌，因为她喜欢赢。

大家在看

KGM转MP3或者FLAC_kgma_kgma格式_FLAC_kgma转换器_kgm转换成flac_亲测完美转换！保证可用。

SPP Workshop.pdf

STM32F4U盘升级程序实例.zip

Easyquery焓熵表焓熵图查询软件V3.0，水和水蒸气焓熵图表查询软件

ST7789V_320x240TFT屏驱动应用可行.zip

最新推荐

【路径规划】基于ADMM求解时间窗车辆路径问题VRPTW附Matlab代码.rar

基于GTD的项目管理系统。.zip

获取本机IP地址的程序源码分析

【权威指南】：Win11笔记本上RTX4080驱动的安装与调试秘籍

windows环境举例

QQ自动发送/回复系统源代码开放

【7步打造Win11深度学习利器】：Tensorflow-GPU与RTX4080终极优化指南

ue画笔画画蓝图版

VB.NET图表曲线组件实现多种图表绘制

【MultiExtractor_Pro实战演练】：8个复杂场景的高效数据提取解决方案