When Xiaoming moved to a new house, he found a significant difference: there was a large flower bed in the backyard of the new house. Xiaoming decided to set up some fences and plant some flowers in his flower bed. For aesthetic reasons, Xiaoming decided to plant flowers only in the spaces between the fences. However, things were not so simple. Xiaoming found that some locations were infested with pests. When a piece of land is infested with pests, neither of the two adjacent pieces of land can be planted with flowers.
Xiaoming decided to use numbers to record the situation of the flower bed: the number 0 represents an empty piece of land, the number 1 represents a fence placed on that piece of land, and the number 9 represents the presence of pests in that piece of land. Xiaoming wants to calculate how many flowers he can plant at most, so he can buy seeds from the flower shop.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains an integer N (1 ≤ N ≤ 25), which represents the number of plots in Xiaoming's flower bed (the shape of the flower bed is a straight line). Then the second line will contain N numbers, each of which can be 0, 1, or 9. | Please output the maximum number of flowers Xiaoming can plant. |
| 5 1 0 0 0 1 | 3 |
| 10 0 1 0 1 0 1 0 0 1 0 | 4 |
| 13 0 1 0 9 1 0 1 0 9 0 0 1 0 | 2 |
Thought Process
Set a variable count initially to 0, representing whether there's a fence encountered, and initialize another variable zero to count the occurrences of 0. If a 0 is encountered and count is 1, it means there's no fence, so this 0 shouldn't be counted. When encountering a fence, set count to 1. While count is 1, the count of flowers can be recorded in zero. Every time a fence is encountered, add the current zero to the answer and reset zero to 0.
When encountering a flower, it's necessary to check whether there are insects before and after it. If there are, zero++ should not be processed. It's important to note that for the first and last positions, we only need to check once for the presence of insects to avoid memory segmentation errors.
Sample Code－ZeroJudge F072: Garden
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, count = 0, zero = 0, ans = 0;
cin >> N;
vector<int>num;
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num.push_back(tmp);
}
for (int i = 0; i<N; i++) {
if (num[i] == 0) {
if (count == 0) continue;
if (i == 0) {
if (num[i+1] != 9) zero++;
continue;
}
if (i == N-1) {
if (num[i-1] != 9) zero++;
continue;
}
if (num[i+1] != 9 && num[i-1] != 9) zero++;
continue;
}
if (num[i] == 1) {
count++;
ans += zero;
zero = 0;
}
}
cout << ans << "\n";
}
//ZeroJudge F072
//Dr. SeanXD