BZOJ4267 : 小强的颜色

首先剔除$1$号心情不能到达的无用心情，然后采用分割法进行DFA的最小化。 每次遍历所有集合，将集合中和集合中第一个心情行为或者转移所在集合不同的心情放入新集合中。 最后按字典序依次给a56爆大奖在线娱乐集合编号即可。 因为最多$O(N)$次分离，每次遍历时间复杂度为$O(NP)$。 故总时间复杂度为$O(N^2P
posted @ 2018-03-04 22:14  Claris  阅读(302)  评论(0)  编辑  收藏  举报