SPOJ 4532 String reduction

題意：

給定一條 ‘a’ 及 ‘b’ 的 string
長度為 N (≤ 300)
現在可重覆以下操作：
把長度為 3 的 substring “xyx” 轉換成 “y”（其中 x, y = ‘a’, ‘b’）
問 string 最多可以縮至多短

---

樣例：

“abaaaaaba” → “bab” → “a”
答案 = 1

---

算法：

O(N³)動態規劃

定義：

S(x,y) := 給定 string 由 index = i 至 j 的 substring
dpA[i][j] := S(i,j) 可以 reduce 至 ‘a’ ... 嗎？
dpB[i][j] := S(i,j) 可以 reduce 至 ‘b’ ... 嗎？

若果 S(x,y) 可以分拆成 三個連續部份
左、中、右部 分別可以 reduce 至 ‘a’、‘a’、‘a’（或 ‘b’、‘a’、‘b’）
則 dpA[x][y] := True
（dpB[x][y] 的也類似地計算）

這樣我們很容易得出 O(N⁴) 的 DP
但對於 N=300 當然不夠快...

增加以下狀態（共４種）優化：

dpXY[i][j] := S(i,j) 可以 reduce 至兩個連續部份，S(i,k) 及 S(k+1,j)，使得 dpX[i][k] 及 dpY[k+1][j] 皆為 True

(X, Y = A 或 B)
便可以把 DP 優化至 O(N³)

我只想到這一步... 應該存在 O(N²) 的 DP...
知道的話請告訴我！

---

題目鏈接：

1. SPOJ 4532 String reduction
2. PKU 3401 String reduction（不過 PKU 的 Test data 是頹廢的...）