題目連結： 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 的狀態總數 -------------------- 這題雖然出題者有寫 tutorial，不過想了一些時間還是沒有看懂 ( tutorial 位址： http://ppt.cc/NNlw ) 目前看完為止的心得是，首先給出一個觀察 假設 A = s[1 .. i - 1], B = s[1 .. i], C = t[1 .. j - 1], D = t[1 .. j] 若要判斷 (i, j) 是否 reachable，如果發現 D 是 A 的 subsequence 或者 B 是 C 的 subsequence，則為了讓 s 可以走到 i 已經足以讓 t 超過 j，反過來也一樣 但是這樣並不夠，進一步可以發現如果 s[1] != t[1] 下了一個指令讓其中一個人前進，比如說 s，則縮短後的 B' = [2 .. i] 有可能就變成 C 的 subsequence 了 如果分別讓 s 或 t 前進都發生這種情況的話 可以發現此時 A 和 C 等長 並且 A 和 C 會分別是 xyxy... 和 yxyx... 的 format 再來得到形如 ...xy, ...yx 的狀態會是 unreachable 的 上面黃色的是無法理解的部份 我自己的想法是的確如果狀態最後長得像 ...xy 和 ...yx 那麼因為 s[i - 1] != t[j - 1]，要進入 (i, j) 狀態 勢必要通過 (i - 1, j) 或 (i, j - 1) 但因為 s[i] = t[j - 1] 且 s[i - 1] = t[j] 所以無論如何，都沒有辦法停留在 (i, j) 但是目前困惑的是，單純這樣就足以找出所有不合法的狀態了嗎 會不會因為 (i, j) 這個狀態走不到，連帶影響到後面 使得某些不是以 ...xy 和 ...yx 做結尾的狀態也變成 unreachable 一點小結是 目標似乎是要證明 (i, j) 是 unreachable iff (1) s[1 .. i] 是 t[1 .. j - 1] 的 subsequence (或反過來) OR (2) s[i - 1] = t[j] AND s[i] = t[j - 1] AND s[i - 1] != t[j - 1] 不過自己推不出來 也不知道怎麼樣從 tutorial 裏的過程得到這個結論 想請問大家是否有些提示 謝謝 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.86.67 ※ 編輯: paae0226 來自: 61.230.225.20 (04/12 21:42) ※ 編輯: paae0226 來自: 61.230.225.20 (04/12 22:59)