CF1479B1 Painting the Array I

如果两种方案末尾两数有一数相同，那么答案较大的方案不劣于答案较小的方案。答案较大的方案只需\textbf{模仿}答案较小的方案即可，在状态变成相同之前答案最多只会少 \(1\)。

所以只需要考虑末尾两数 \(a,b\) 与新进来的数 \(c\) 各不相同时该替换哪个。

假设 \(a\) 下次出现的位置早于 \(b\)，当下一次 \(a\) 出现时：

• 替换 \(b\) 的方案中的 \(a\) 已被替换，因为这期间 \(b\) 没出现过，所以替换 \(a\) 的方案可以模仿替换 \(b\) 的方案使得答案和状态相同。
• 替换 \(b\) 的方案中的 \(a\) 未被替换，也就是说这种方案一直在替换另一个数
  • 中间存在相同数的替换。在发生之前另一种方案一直模仿，发生时另一种方案选择替换 \(b\) 使得答案变大 \(1\)，根据最前面那个结论另一种方案不会更劣。
  • 中间不存在相同数的替换。在最后一步之前另一种方案一直模仿，两种方案最终变成了 \(\{a,a\}\) 和 \(\{a,b/d\}\)，其中 \(d\) 是前一步的数。考虑再下一步进来的数 \(e\)，\(\{a,a\}\) 变成 \(\{a,e\}\)，而 \(\{a,b/d\}\) 中 \(b\) 或 \(d\) 肯定有一个不等于 \(e\)，同样能变成 \(\{a,e\}\) 并且使得答案变大 \(1\)，不会更劣。

所以各不相同时替换下次出现位置靠前的即可，B2 改成靠后的即可。