路径上的传播方向

思路

将数组看作一条路径。每次免费涂色，都选择一条从已经变红的位置指向新位置的边。每个位置最多被免费涂色一次，所以入度最多为 $1$；位置 $i$ 最多帮助 $a_i$ 个相邻位置变红，所以出度最多为 $a_i$。

路径没有环。只要选出的有向边满足这两个局部限制，每个连通分量就恰好有一个入度为 $0$ 的位置。支付一枚硬币把它涂红，再按从父亲到孩子的顺序传播，就能实现该分量的全部边。因此答案等于合法选边方案中入度为 $0$ 的位置数的最小值。

做法

每条相邻边有三种状态：不选、从左向右、从右向左。扫描位置 $i$ 时，枚举其左边和右边的状态，就能确定它的入度和出度。

用 $dp[c]$ 表示已经检查完左侧所有位置，且当前左边的状态为 $c$ 时的最少硬币数。枚举右边状态 $d$，当入度不超过 $1$、出度不超过 $a_i$ 时，更新下一层 $dp[d]$；如果位置 $i$ 的入度为 $0$，代价加 $1$。

数组外侧的边必须是不选。初始只有“不选”状态的值为 $0$，最后取“不选”状态的结果。

正确性证明

实际操作中，每个免费变红的位置都有唯一的来源，且一个位置帮助邻居的次数不超过其初值，所以每个实际方案都对应满足局部限制的有向边方案。付费的位置恰好是没有入边的位置。

反过来，合法选边方案的每个连通分量是树。它有的边数比点数少一，且每个点入度至多为一，因此恰好存在一个没有入边的根，其余点入度均为一。由于不存在有向环，从根出发依次涂色即可实现所有边；出度限制保证每个位置的数值够用。

动态规划枚举了每一条边的全部状态，并在处理其相邻位置时完整检查局部限制。每个位置恰好计算一次费用，故它在所有可行操作方案中取到了最小花费。

复杂度

每个位置只枚举 $3\times3$ 种状态组合，时间复杂度为 $O(n)$。滚动数组额外空间为 $O(1)$，输入数组使用 $O(n)$ 空间。

部分分思路

极小规模可以直接搜索每个位置是蓝色还是红色，以及红色位置的剩余数值。免费操作的边权为零，付费操作的边权为一，使用 0-1 BFS 求最短路。

中等规模可以把最终传播分量视为连续区间，枚举区间划分。一个区间能由一枚硬币覆盖，当且仅当它长度为一，或内部没有零，且两端同时为零时内部至少有一个 $2$。这是因为零不能继续传播；需要同时向两边传播时，可以从某个 $2$ 开始，否则可以从合适的端点开始。预处理零和二的前缀计数后，可以在常数时间检查一个区间，得到 $O(n^2)$ 的划分 DP。

如果所有数都不超过一，每个极大连续正数段至少需要一枚硬币，并能额外覆盖至多一个相邻零。从左到右处理各段，优先覆盖尚未覆盖的左侧零，否则覆盖右侧零。这是在路径上匹配正数段与相邻零：左侧零之后不会再有机会被新的段覆盖，因此优先选择它不会损失最优性。最后给剩余零单独付费。该贪心完整处理这一子任务，但数值为二时，一个段可能同时向两边传播，需要一般算法。