算法 POJ1953

一、题目大意

世界杯噪音

背景
“KO-RE-A， KO-RE-A” 在他们的球队进入本国的 FIFA 世界杯半决赛后，54.000 名快乐的球迷大喊。但是，尽管他们的兴奋是真实的，但韩国人民天生仍然非常有组织性。例如，他们组织了巨大的小号（听起来像吹船的号角）来支持他们的球队在球场上比赛。球迷希望在整个比赛中保持噪音水平恒定。
喇叭由压缩气体作。但是，如果您不停地吹响小号 2 秒钟，它就会坏掉。因此，当小号发出声音时，一切都很好，但在小号暂停时，粉丝们必须高呼“KO-RE-A”！
比赛前，一群球迷聚集在一起，决定一个高呼模式。该模式是 0 和 1 的序列，其解释方式如下：如果模式显示 1，则吹响小号。如果显示 0，球迷会高呼“KO-RE-A”。为了确保小号不会中断，该模式中不允许有两个连续的 1。
问题
给定一个正整数 n，确定此长度的不同吟唱模式的数量，即确定不包含相邻 1 的 n 位序列的数量。例如，对于 n = 3，答案是 5（序列 000、001、010、100、101 是可接受的，而 011、110、111 则不可接受）。

输入

第一行包含方案数。
对于每个场景，您都会在一行上得到一个小于 45 的正整数。

输出

每个方案的输出都以包含 “Scenario #i：”的行开头，其中 i 是从 1 开始的方案编号。然后打印一行，其中包含没有相邻 1 的 n 位序列的数量。用空行终止方案的输出。

样本输入

2

3

1

示例输出

Scenario #1:

5

Scenario #2:

2

二、题意理解与分析

这是一道计算特定二进制序列数量的问题，并非运用特定经典算法（如dijkstra算法等）的变形题。问题中已知需要确定长度为正整数n（n < 45）且不包含相邻1的n位二进制序列的数量，这些二进制序列代表球迷的欢呼模式，其中1表示吹响小号，0表示高呼“KO - RE - A” ，由于小号不能连续吹响2秒，所以序列中不允许出现两个连续的1。我们需要根据给定的多个正整数n，计算每个n对应的不包含相邻1的n位序列的数量。解题的关键在于使用动态规划的方法，通过定义两个数组`dp0`和`dp1`分别记录以0和1结尾的不包含相邻1的序列的数量，利用状态转移方程递推计算出不同长度序列的满足条件的数量，最后将以0和1结尾的序列数量相加得到最终结果。

三、算法思路分析

首先初始化两个数组`dp0`和`dp1`，用于分别记录以 0 和 1 结尾的不包含相邻 1 的 n 位序列的数量，数组长度为`n + 1`并初始元素值都为 0。接着处理初始情况，当`n`为 1 时，以 0 结尾和以 1 结尾的序列都各有 1 种，即`dp0[1] = 1`，`dp1[1] = 1`。然后从 2 开始遍历到`n`，对于每个长度`i`，依据状态转移方程更新`dp0`和`dp1`数组的值，以 0 结尾的序列数量`dp0[i]`等于前一个长度以 0 结尾的序列数量`dp0[i - 1]`加上前一个长度以 1 结尾的序列数量`dp1[i - 1]`；以 1 结尾的序列数量`dp1[i]`等于前一个长度以 0 结尾的序列数量`dp0[i - 1]`。最后将`dp0[n]`和`dp1[n]`相加，得到长度为`n`的不包含相邻 1 的 n 位序列的总数。在主函数中，先读取方案数，对每个方案读取对应的`n`值，调用`countSequences`函数计算结果，并按照指定格式输出结果，每个方案输出后用空行分隔。

四．源代码

五．总结

通过编写解决“世界杯噪音”问题的程序，巩固了对动态规划这一算法思想的理解与运用。在代码中利用数组`dp0`和`dp1`分别记录以0和1结尾的不包含相邻1的序列数量，并通过状态转移方程进行递推计算。虽未涉及经典算法如dijkstra算法等，但此次实践锻炼了对实际问题进行抽象建模并运用合适算法解决的能力，让我明白不能局限于固有思维，要根据不同问题的特点灵活选择方法，牢记动态规划的状态定义、状态转移方程等关键要素，从而扩展解题思维的广度。例如本题根据不允许相邻1的规则合理定义状态和转移方程来计算序列数量，为今后解决类似的组合计数问题积累了宝贵经验。