我不会贪婪证明，但是我们可以用动态规划的思想来写这道题，为什么可以呢？因为每一个点只会由前一个位置的情况来决定当前本身的情况。我们设 d p i , j dp_{i,j} dpi,j 表现为第 i i i 位置，第 j j j 个位置确定添补 # 而且包管和前面联通的最小花费， j j j 取 0 0 0 或 1 1 1，分别表现 i i i 位置的上层还是下层。
由上面的图，我们可以看到，当前如果为 #，要么由前面那个直接转移(路径①)，要么就由前面另一个方向转移(路径②)。我们设蓝色所在位置为 ( i , 0 ) (i,0) (i,0) 。
那么路径①就是由前面 ( i − 1 , 1 ) (i-1,1) (i−1,1) 转移到 ( i , 0 ) (i,0) (i,0)。
那么路径②就是由前面 ( i − 1 , 1 ) (i-1,1) (i−1,1) 先转移到 ( i , 1 ) (i,1) (i,1) 再转移到 ( i , 0 ) (i,0) (i,0) 。
我们可以根据上面所计划的 d p dp dp 状态可以知道，路径①只会只由前面 ( i − 1 , 0 ) (i-1,0) (i−1,0) 确定，而当前这个点已经包管了为 # 且与前面联通，而且花费最小，那么我们只需要考虑 ( i , 0 ) (i,0) (i,0) 这一位是否为 # 即可，如果不为 # 则需要贡献加 1 1 1，否则直接转移。
而对于路径②，我们当然不可以直接由 ( i , 1 ) (i,1) (i,1) 转移，我们就需要考虑 ( i − 1 , 1 ) (i-1,1) (i−1,1)，因为这个点的 d p dp dp 值包管了它此时为 # 且与前面联通，而且花费最小，那么，如果要通过路径②转移的话，我们就要考虑到 ( i , 1 ) (i,1) (i,1) 是否为 #，而且还需要考虑到 ( i , 0 ) (i,0) (i,0) 这一个是否为 #，即可盘算出对应的 d p dp dp 值。
对于下层的话，类比上层的做法一样可以求解，可以本身模仿试一下。 所以，我们可以得到最终的转移方程如下：
d p i , 0 = min ( d p i − 1 , 0 , d p i − 1 , 1 + ( s i , 1 ≠ # ) ) + ( s i , 0 ≠ # ) dp_{i,0} = \min(dp_{i-1,0}, dp_{i-1,1} + (s_{i,1} \neq \#)) + (s_{i,0} \neq \#) dpi,0=min(dpi−1,0,dpi−1,1+(si,1=#))+(si,0=#)
d p i , 1 = min ( d p i − 1 , 1 , d p i − 1 , 0 + ( s i , 0 ≠ # ) ) + ( s i , 1 ≠ # ) dp_{i,1} = \min(dp_{i-1,1}, dp_{i-1,0} + (s_{i,0}\neq \#)) + (s_{i,1} \neq \#) dpi,1=min(dpi−1,1,dpi−1,0+(si,0=#))+(si,1=#)
a n s = min ( d p e n d , 0 , d p e n d , 1 ) ans=\min(dp_{end,0},dp_{end,1}) ans=min(dpend,0,dpend,1)
我们得到了一个转移方程，此中 s i , j s_{i,j} si,j 表现的是 i i i 位置对应的上下层字符， j j j 取 0 , 1 0,1 0,1， 0 0 0 为上层， 1 1 1 为下层。但是现在另有一个问题就是，如果从最开始进行 d p dp dp 转移，由于第 i i i 位置之前如果没有检测器，我们是不需要添加额外的检测器，所以我们需要找到第一个存在检测器的位置，以及末了一个位置的检测器位置即可。如果都找不到，阐明没有检测器，虽然标题说了，已经存在一些检测器，我们为安全起见，可以特判一下这个情况。末了的答案，肯定就是由末端的情况的最小值啦~，复杂度为 O ( n ) O(n) O(n)。
对于 d p dp dp 的初始值，只需要看当前是否为 #，为 # 则是 0 0 0，否则是 1 1 1 即可，然后就可以美美地敲一发 A C AC AC 啦~
