A102290 雾港学宫的能量链 题解
题目分析
我们有一个由 (n) 个符号元件组成的能量链，每个元件有一个数值。可以从中选择一个非空子序列，计算该子序列的前缀乘积符号变化次数。我们的目标是尽量减少符号变化次数，并统计最小符号变化次数对应的子序列数量。
关键概念：
1. 符号变化次数：指的是前缀乘积的符号变化次数。我们只关心每个前缀乘积的符号（正、负或零）。如果前缀乘积的符号与上一个前缀乘积符号不同，则符号变化次数加 1。
2. 子序列：我们可以从序列中选出一个非空子序列，保持元素的相对顺序。我们需要找到符号变化次数最小的子序列，并统计其数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 关键分析
我们关注的是前缀乘积的符号变化次数。首先，符号变化只会在乘积从正变负或者从负变正时发生。零对符号变化没有影响，因为零的乘积总是零，符号始终为零。因此，零的元素可以随意选择，不影响符号变化次数。
对于非零元素：
* 如果元素是正数，它会继续维持前面的符号。
* 如果元素是负数，它会改变符号。
我们的目标是通过选择子序列，使得符号变化次数最小。为了避免符号的变化，我们希望尽量选择符号不变的子序列。
2. 动态规划优化
我们使用动态规划和前缀和的方式来优化计算过程：
* 我们首先计算每个位置之后的正数的数量，便于我们高效地选择符号变化次数最小的子序列。
* 然后，计算每个非零元素对符号变化次数的贡献。
* 计算包含零的子序列的选择方式。
最终，我们计算符号变化次数最小的子序列的数量，并输出结果。
3. 解决步骤
1. 计算每个位置之后的正数数量。
2. 计算每个非零元素对符号变化次数的贡献。
3. 计算包含零的子序列的选择方式。
4. 输出最小符号变化次数和满足最小符号变化次数的子序列数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复杂度分析
* 时间复杂度：(O(n))，我们通过一次遍历计算前缀和，处理所有正数和零的子序列。
* 空间复杂度：(O(n))，我们使用了一些辅助数组来存储正数计数、2的幂次、结果等。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例解释
输入：
1. 初始化：我们有 5 个符号元件，它们的值为 ([2,−3,0,−5,4][2, -3, 0, -5, 4][2,−3,0,−5,4])。
2. 计算正数的子序列贡献：首先计算每个位置之后的正数的数量。然后，计算每个非零元素对符号变化次数的贡献。
3. 计算零的子序列贡献：零对符号没有影响，因此它的选择方式比较灵活。
4. 最终结果：最小符号变化次数为 0，且有 11 个不同的子序列满足该条件。
输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ENGLISH VERSION
A102290 FOG HARBOR ACADEMY ENERGY CHAIN PROBLEM
PROBLEM ANALYSIS
We have a chain of (n) energy elements, each with a value (a[i]) (which could be positive, negative, or 0). You can select a non-empty subsequence from the sequence, and the goal is to minimize the number of sign changes in the prefix products of that subsequence.
KEY CONCEPTS:
1. Sign Change Count: This refers to the number of times the sign of the prefix product changes. We only care about the sign (positive, negative, or zero) of each prefix product. If the sign changes from the previous prefix product, the sign change count increases by 1.
2. Subsequences: We are asked to find the subsequences that minimize the sign change count and then count how many such subsequences exist.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
APPROACH
1. KEY INSIGHT
We are concerned with the sign change count of the prefix products. A sign change happens when the product flips from positive to negative or vice versa. Zero does not affect the sign since the product is zero, so zero elements can be freely chosen.
For non-zero elements:
* Positive elements will maintain the current sign.
* Negative elements will flip the sign.
Our goal is to minimize the sign changes by choosing subsequences where the sign remains consistent as much as possible.
2. DYNAMIC PROGRAMMING OPTIMIZATION
We can solve this using dynamic programming and prefix sums:
* First, compute the number of positive numbers after each position, which helps in efficiently choosing subsequences that minimize the sign change count.
* Next, calculate the contribution of each non-zero element to the sign change count.
* Finally, calculate the number of valid subsequences that contain zero elements.
3. STEPS
1. Compute the number of positive numbers after each position.
2. Calculate the contribution of each non-zero element to the sign change count.
3. Calculate the ways to choose subsequences containing zero elements.
4. Output the minimum sign change count and the number of subsequences achieving this count.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CODE IMPLEMENTATION
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TIME COMPLEXITY:
* Time Complexity: (O(n)) — We compute the prefix sum and sign change contributions in linear time.
* Space Complexity: (O(n)) — We use auxiliary arrays to store intermediate results.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
EXAMPLE EXPLANATION
Input:
1. Initialization: We have 5 elements: ([2, -3, 0, -5, 4]).
2. Calculate Positive Subsequences: First, compute the number of positive elements after each position. Then, calculate each non-zero element's contribution to the sign change count.
3. Zero Contributions: Zero elements do not affect the sign but contribute to the subsequence count.
4. Final Result: The minimum sign change count is 0, and the number of subsequences achieving this count is 11.
Output:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CONCLUSION
This problem can be efficiently solved using dynamic programming and prefix sums, reducing the problem complexity to (O(n)), which is feasible even for large inputs.
