[问题] CF R162 Div.1 Problem D

楼主: paae0226 (paae0226)   2013-04-12 16:56:12
题目连结: http://ppt.cc/avSY
题意:
给予两个由 R, G, B 所组成的字串 s (|s| <= 10^6) 和 t (|t| <= 10^6)
一开始有两个人分别位在 s[1] 和 t[1] 上 (index 为 1-base)
现在可以对这两个人下指令,比如 “站在 R 上的人前进一格”
此时如果 s[1] = R,则第一个人必须走到 s[2],站在 t 上的人亦同
所以如果两个人所站的 s[i] 和 t[j] 颜色一样,则下达该颜色会让两个人同时前进
如果有某一个人已经站在 sequence 的尾巴 (s[length(s)] 或 t[length(t)])
则不能下 s[length(s)] 或 t[length(t)] 那格的颜色
也就是不能下会让某一个人走出自己所处 sequence 的命令
现在定义一个状态 (i, j) 是 reachable 为
存在一个命令 sequence I,使从 s[1] 和 t[1] 出发,按照 I 的命令走完之后
可以使两人最后分别停在 s[i] 和 t[j]
否则为 unreachable
问 reachable 的状态总数

Links booklink

Contact Us: admin [ a t ] ucptt.com