USACO beads问题代码解析

" Broken Necklace 是一个USACO（美国计算机奥林匹克竞赛）中的编程题目，涉及到字符串处理、数组操作和动态规划的概念。代码用C++编写，实现了寻找破损项链上最长无色珠子连续串的解决方案。" 该代码解决了一个名为 "Broken Necklace" 的问题，其背景是有一串珠子项链，由红色（'r'）和蓝色（'b'）珠子组成，已知项链已经断裂，现在需要找到最长的一段，使得在这段项链中，红色和蓝色珠子都不相邻。这个问题可以通过动态规划的方法来解决。 1. **输入处理**： - 代码首先通过`fscanf`读取输入文件"beads.in"中的整数`n`，代表珠子数量，以及字符串`s`，表示珠子的颜色序列。 - `tmp`变量用于临时存储输入，然后将其复制到`s`，并把原始字符串与自身连接（`strcat`），这样可以简化后续处理，因为项链可以双向遍历。 2. **动态规划初始化**： - 定义两个数组`rl`和`bl`，分别记录从当前位置向右看连续的红色珠子和蓝色珠子的数量。 - 同样定义`rr`和`br`，记录从当前位置向左看连续的红色和蓝色珠子数量。 - 数组初始化，`bl[0]=rr[0]=0`，表示起始位置没有连续的珠子。 3. **向右遍历**： - 遍历字符串，根据当前字符更新`rl`和`bl`数组，计算当前位置向右的最大无色珠子连续串长度。 4. **向左遍历**： - 再次遍历字符串，但这次从后向前，更新`rr`和`br`数组，计算当前位置向左的最大无色珠子连续串长度。 5. **最大无色串长度计算**： - 初始化`m`为0，表示最长无色珠子连续串长度。 - 遍历所有位置，计算当前位置左右两边的最大无色珠子串长度之和，并更新`m`。 6. **考虑项链断裂**： - 由于项链可以断开，因此最长无色串长度可能小于珠子总数`n`，所以`m`的值应该限制在`n`以内。 - 最后将结果`m`输出到"beads.out"文件中。 这个代码展示了如何利用动态规划策略解决实际问题，通过对字符串进行两次遍历，分别计算从当前位置向左和向右的最大无色珠子连续串，然后找到这些串的最大长度。这种算法在解决链状结构的问题时非常有效。