做法就是动态规划结合单调队列优化，设 $f_{i,s}$ 表示第 $i$ 个王朝的统治者是 $s$ 时的最小可疑度。

状态转移方程不难写出 $f_{i,s}=\min\limits_{j=0}^{i-1} f_{j,s}+\operatorname{cost}(i,j)$，其中 $\operatorname{cost}(i,j)$ 表示统治者 $s$ 连续统治的两个王朝是 $i,j$ 时的可疑度。

考虑单调队列优化。

从小到大枚举 $i$ 表示王朝 $i$，枚举转移的 $s$，用两个单调队列分别表示以 $s=0/1$ 为结尾的单调队列。

对 $s=0/1$ 将 $s'=1/0$ 的单调队列中满足下界限制的新位置加入，删去不满足上界的位置删除。考虑异色转移的两种情况，一种队列非空，直接转移，另一种是从虚拟节点 $0$ 转移。

然后就是维护全局加 $v$ 操作，当当前位置可以与前一个位置连续做 $s$ 时，$v=1$，否则 $v\rightarrow+\infty$，直接把当前答案减 $v$，因为只有当前答案不需要另外加 $v$，然后维护全局标记，在全局标记上加 $v$。

这么做，还有一点要注意，就是当 $n$ 也被处理完后，所维护的 $f_{i,s}$ 变成了在以 $s$ 王朝为结尾，最后一段是 $[i,n]$ 的最小可疑度，假设 $f_{i,s}$ 从 $f_{j,s'}$ 转移来，那么 $[j,i)$ 都是 $s'$。

最后枚举求出答案即可。