https://codeforces.com/problemset/problem/49/E

題意：

DNA序列的一個(gè)字符會(huì)被替換成另外的兩個(gè)。變化a[i] → b[i] c[i]

?每一種變化均可以無限次發(fā)生。總共有n種允許的變化。 科學(xué)家們表示，

?如果一個(gè)DNA序列s3 在整個(gè)進(jìn)化過程中可以最終變?yōu)閟1? 和s2 ，

?那么DNA序列分別為s1? 和s2 的兩個(gè)生物就會(huì)有一個(gè)共同祖先。現(xiàn)在給出s1

? 和s2，你的任務(wù)是弄清楚分別擁有這兩種DNA序列的生物是否有共同祖先。如果存在，

? 你需要找出所有共同祖先中最短長度。

?題解：

ok[s][st][ed]|= 1<<c-'a'? ?代表 字符串區(qū)間s[st,ed]可以由單一的字母c變換得到，

?c可以有多種選項(xiàng)，ok[s][st][ed]為字符狀態(tài)壓縮。

dp[i][j]代表 對(duì)于S串前i個(gè)元素和對(duì)于T串前j個(gè)元素最短的初始字符串長度。

狀態(tài)轉(zhuǎn)移

dp[i][j]=min(dp[i][j],dp[i?k1][j?k2]+1)(k1，k2表示s1和s2最后分別連續(xù)k1和k2的長度可以縮成同一字母)