题目描述

难度分:$1700$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 2)$。

最初，数组的每个元素都是蓝色的。有以下两种类型的操作：

• 支付一枚硬币，选择一个蓝色元素，将其涂成红色。
• 选择一个不等于$0$的红色元素和与其相邻的一个蓝色元素，将红色元素的数值减少$1$，然后将蓝色元素涂成红色。

把每个元素都涂成红色，最少要支付多少金币？

输入样例$1$

3
0 2 0

输出样例$1$

1

输入样例$2$

4
0 0 1 1

输出样例$2$

2

输入样例$3$

7
0 1 0 0 1 0 2

输出样例$3$

4

算法

贪心

以为是线性DP，搞了好一阵结果WA了，再定睛一看发现直接贪心就能做，决策是固定的。

粗略分析一下，对于一段非零的格子，如果其中有一个$2$，就可以先把$2$染红，再从这个$2$往两边免费染色，直到囊括掉这段非零区间边界的两个$0$。如果其中没有$2$，那么就是全$1$段，与包括$2$的非零段类似，但是全$1$段只能囊括掉一个边界的$0$（从边界的一个$1$开始染色，染到另一个边界）。因此我们统计数组中非零段的情况，每个非零段需要染色一次，有$2$的非零段最多带两个$0$，全$1$段带一个$0$，最后还剩下多少个孤立的$0$就还要染色多少次。

实现的时候可以从左往右遍历数组，分情况讨论：

1. 如果$a[i]=0$，检查它的后面是否有非零段，没有就直接增加染色次数。有就检查非零段中有没有$2$，有的话增加一次染色，$i$跳到下一个$0$的右边，否则$i$只能跳到下一个$0$的位置，下一个$0$不能被这个非零段连带染色。
2. 如果$a[i] \neq 0$，此时一定是一个非零段的开头，看这个非零段能延伸多远，染色一次，带上下一个$0$，$i$跳到下一个$0$的右边。

复杂度分析

时间复杂度

遍历一遍数组就可以求得答案，时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

$python$代码

n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i < n:
    if a[i] == 0:
        j = i + 1
        mx = 0
        while j < n and a[j] > 0:
            mx = max(mx, a[j])
            j += 1
        if j < n:
            ans += 1
            i = j
            if mx == 2:
                i = j + 1
        else:
            ans += 1
            i = j
    else:
        j = i + 1
        while j < n and a[j] > 0:
            j += 1
        ans += 1
        i = j + 1
print(ans)