题目描述 Description 农场主小陈种植了 𝑁 N 株桃树排成一列( 1 ≤ 𝑁 ≤ 3 ⋅ 1 0 5 1≤N≤3⋅10 5 )。这些桃树会以一种神奇的方式互相传播花粉。 具体来说,有一些树在第 1 1天白天会被蜜蜂传播花粉并开花,有些则没有被传播花粉,没有开花。每到夜晚,开花的树会将花粉传播给它左右两边的树(如果这些树存在的话)。一旦树被传粉,它就会立即并持续处于开花状态。 经过一些晚上,小陈发现有很多树都开放了花朵。现在他在思考这样一个问题,最少有多少棵树一开始就被蜜蜂传播了花粉。 输入描述 Input Description 第一行为一个整数 𝑁 N,即农场主拥有的桃树数量。 接下来一行,包含长度为 𝑁 N 的由 1 1 和 0 0 组成的位串。其中 1 1 表示一个开花的桃树, 0 0 表示一个一直没有开花的桃树。 输出描述 Output Description 输出一个整数,表示最少有多少个桃树是可能最初开花的桃树。 样例输入 Sample Input 【样例1】 6 111111 【样例2】 7 0101110 样例输出 Sample Output 【样例1】 1 【样例2】 4 数据范围及提示 Data Size & Hint 样例1,初始是100000,经过5夜后所有桃树都开花,变为111111。当然初始状态为其它桃树是1时,也可以得到同样的答案。 样例2可以证明只有0101110这样唯一的一个初始状态。 测试点性质 测试点 1 − 4 1−4 满足一定有一个单独的1不和其它1相连。 测试点 5 − 1 0 5−10 没有额外限制。 编程语言: C++ 14
理解问题题目描述 Description 农场主小陈种植了 𝑁 N 株桃树排成一列( 1 ≤ 𝑁 ≤ 3 ⋅ 1 0 5 1≤N≤3⋅10 5 )。这些桃树会以一种神奇的方式互相传播花粉。 具体来说,有一些树在第 1 1天白天会被蜜蜂传播花粉并开花,有些则没有被传播花粉,没有开花。每到夜晚,开花的树会将花粉传播给它左右两边的树(如果这些树存在的话)。一旦树被传粉,它就会立即并持续处于开花状态。 经过一些晚上,小陈发现有很多树都开放了花朵。现在他在思考这样一个问题,最少有多少棵树一开始就被蜜蜂传播了花粉。 输入描述 Input Description 第一行为一个整数 𝑁 N,即农场主拥有的桃树数量。 接下来一行,包含长度为 𝑁 N 的由 1 1 和 0 0 组成的位串。其中 1 1 表示一个开花的桃树, 0 0 表示一个一直没有开花的桃树。 输出描述 Output Description 输出一个整数,表示最少有多少个桃树是可能最初开花的桃树。 样例输入 Sample Input 【样例1】 6 111111 【样例2】 7 0101110 样例输出 Sample Output 【样例1】 1 【样例2】 4 数据范围及提示 Data Size & Hint 样例1,初始是100000,经过5夜后所有桃树都开花,变为111111。当然初始状态为其它桃树是1时,也可以得到同样的答案。 样例2可以证明只有0101110这样唯一的一个初始状态。 测试点性质 测试点 1 − 4 1−4 满足一定有一个单独的1不和其它1相连。 测试点 5 − 1 0 5−10 没有额外限制。 编程语言: C++ 14
已完成理解「题目描述 Description 农场主小陈种植了 𝑁 N 株桃树排成一列( 1 ≤ 𝑁 ≤ 3 ⋅ 1 0 5 1≤N≤3⋅10 5 )。这些桃树会以一种神奇的方式互相传播花粉。 具体来说,有一些树在第 1 1天白天会被蜜蜂传播花粉并开花,有些则没有被传播花粉,没有开花。每到夜晚,开花的树会将花粉传播给它左右两边的树(如果这些树存在的话)。一旦树被传粉,它就会立即并持续处于开花状态。 经过一些晚上,小陈发现有很多树都开放了花朵。现在他在思考这样一个问题,最少有多少棵树一开始就被蜜蜂传播了花粉。 输入描述 Input Description 第一行为一个整数 𝑁 N,即农场主拥有的桃树数量。 接下来一行,包含长度为 𝑁 N 的由 1 1 和 0 0 组成的位串。其中 1 1 表示一个开花的桃树, 0 0 表示一个一直没有开花的桃树。 输出描述 Output Description 输出一个整数,表示最少有多少个桃树是可能最初开花的桃树。 样例输入 Sample Input 【样例1】 6 111111 【样例2】 7 0101110 样例输出 Sample Output 【样例1】 1 【样例2】 4 数据范围及提示 Data Size & Hint 样例1,初始是100000,经过5夜后所有桃树都开花,变为111111。当然初始状态为其它桃树是1时,也可以得到同样的答案。 样例2可以证明只有0101110这样唯一的一个初始状态。 测试点性质 测试点 1 − 4 1−4 满足一定有一个单独的1不和其它1相连。 测试点 5 − 1 0 5−10 没有额外限制。 编程语言: C++ 14」
展开阅读网页
这个问题是一个典型的动态规划问题,我们需要找出最少有多少棵树在第一天就被蜜蜂传播了花粉。根据题目描述,我们可以知道以下几点:
- 桃树排成一列,并且每棵树要么开花,要么不开花。
- 每棵树如果开花,就会在夜晚将花粉传播给左右两边的树。
- 我们需要找出最少有多少棵树在第一天就开花,以保证所有开花的树最终都能开花。
根据这些信息,我们可以采用以下步骤来解决问题:
步骤 1:理解问题
首先,我们需要理解题目的要求,即找出最少有多少棵树在第一天就开花。这个问题可以通过观察桃树的开花状态来解决。
步骤 2:分析桃树的开花状态
我们需要分析桃树的开花状态,特别是那些没有开花的桃树。因为如果一个桃树一直没有开花,那么它两边的桃树在第一天就不可能开花,否则这个桃树最终也会开花。
步骤 3:使用动态规划
我们可以定义一个动态规划数组 dp
,其中 dp[i]
表示以第 i
棵树为最后一个开花的桃树时,需要的最少开花桃树数量。我们可以从左到右遍历桃树,更新 dp
数组。
步骤 4:更新动态规划数组
当我们遍历到第 i
棵树时,我们需要考虑以下几种情况:
- 如果第
i
棵树开花了,那么dp[i]
可以等于dp[i-1]
(如果第i-1
棵树也开花了)或者等于dp[i-2] + 1
(如果第i-1
棵树没有开花,但第i-2
棵树开花了)。 - 如果第
i
棵树没有开花,那么dp[i]
必须等于dp[i-1] + 1
,因为我们需要增加一个开花的桃树来保证第i
棵树最终能开花。
步骤 5:计算结果
最后,我们需要返回 dp
数组的最后一个元素,即 dp[N-1]
,这表示在整个桃树序列中,最少需要多少棵树在第一天就开花。
代码实现
以下是使用 C++ 14 编写的代码示例:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> trees(N);
for (int i = 0; i < N; ++i) {
cin >> trees[i];
}
vector<int> dp(N, 0);
int result = 0;
for (int i = 0; i < N; ++i) {
if (trees[i] == 1) {
if (i == 0 || trees[i - 1] == 0) {
dp[i] = 1;
} else {
dp[i] = dp[i - 1];
}
result = max(result, dp[i]);
} else {
dp[i] = result + 1;
}
}
cout << result << endl;
return 0;
}