[CSP-S 2021] 括號序列 題解

Link

對區間 DP 的理解加深了！

常規地，我們設 \(f_{l, r}\) 表示區間 \([l, r]\) 為合法序列的方案數，并從小到大轉移。這些內容不太夠我們轉移啊，而且由于合并順序的不同還會(huì )出現重復的情況：

\[\begin{aligned} \color{red}(A)S(B) \color{green}S(C) \\ \color{green}(A)S \color{red}(B)S(C) \\ \end{aligned} \]

怎么處理這個(gè)問(wèn)題呢？觀(guān)察一下題目，合法序列可以分為：

1. \(\rm (), (S)\)
2. \(\rm AB, ASB\)
3. \(\rm (A), (SA), (AS)\)

重新設計狀態(tài)，增加一維限制、或者分開(kāi)統計：令 \(f_{l, r}\) 表示 \([l, r]\) 為合法序列且 \(l, r\) 所對應字符為匹配的括號；\(g_{l, r}\) 表示 \([l, r]\) 為合法序列且 \(l, r\) 所對應字符不是匹配的括號。分別對應上面的 1, 3 和 2 類(lèi)。分開(kāi)統計，最終答案為 \(f_{1, n} + g_{1, n}\)，繞過(guò)了這個(gè)去重的難點(diǎn)。

令當前的區間長(cháng)度為 \(len\)，同時(shí) \(O(n^2)\) 地預處理出 \(h(l, r)\) 表示 \([l, r]\) 是否全為 \(\rm */?\)。邊界情況為 \(len = 2\) 時(shí) \(f_{l, r} = 1\)，如果 \(l, r\) 中有任意一個(gè)不為合法括號則直接跳過(guò)。

開(kāi)始轉移

\[f_{l, r} = f_{l, r} + \begin{cases} [h(l, r)] &\text{(S)} \\ f_{l + 1, r - 1} + g_{l + 1, r - 1} &\text{(A)} \\ \sum_{i = 1}^{k} (f_{l + i + 1, r - 1} + g_{l + i + 1, r - 1}) \times h(l + 1, l + i) &\text{(SA)} \\ \sum_{i = 1}^{k} (f_{l + 1, r - i - 1} + g_{l + 1, r - i - 1}) \times h(r - i, r - 1) &\text{(AS)} \\ \end{cases} \]

這四個(gè)處理就是字面意思的轉移，按照方程式理解就可以了。另外對于 \(\rm ASB, AB\) 有：

\[g_{l, r} = g_{l, r} + \sum_{l \lt i \lt j \lt r, j - i - 1 \leq k} \left( (f_{l, i} + g_{l, i}) \times f_{j, r} \right) \times h(i + 1, j - 1) \]

特判一下 \(\rm AB\) 的情況，定義 \(h(l, l - 1) = 1\)。注意到我們這里欽定 \(B\) 為一三類(lèi)，為什么這樣是對的呢？注意到如果我們不欽定，顯然一個(gè)合法序列會(huì )有多種拆解方式。這種限制方法是有正確性保證的：

1. 完備性：思考一下，任何合法的 \(\rm ASB\) 子串必定能被拆分成形如“封閉/不封閉+符合條件數量*+封閉”的分解方式
2. 不重復性：由于強制欽定了 B 的組成方式，每個(gè)序列的分解方式變得唯一了：我們總是選擇最外層的括號作為 B 的邊界，這確保了不會(huì )出現多種解析方式對應同一個(gè)序列的情況
3. 邊界正確：通過(guò)處理 \(h(l, l - 1) = 1\) 保證了空序列的正確性

但是你發(fā)現最后這個(gè) \(g\) 的轉移是 \(O(n^4)\) 的，怎么優(yōu)化呢？注意到若 \(i\) 增減 \(1\) 則可取的 \(j\) 的范圍也對應地僅增減 \(1\)，對于固定的 \(l, r\)，當 \(i\) 增加時(shí)：

• \(j\) 的下界從 \(i + 1\) 變?yōu)?\(i + 2\)
• \(j\) 的上界從 \(\min(i + k + 1, r - 1)\)（因為星號序列長(cháng)度要求為 \(j - i - 1 \leq k\)，考慮兩個(gè)括號對位置的占用） 變?yōu)?\(\min(i + k + 2, r - 1)\)

維護 \(to_i\) 表示 \(\rm A\) 于 \(i\) 結束并于 \(j\) 開(kāi)始 \(B\) 時(shí) \(j\) 的最大可能取值，再維護一個(gè)滑動(dòng)窗口 \(w\) 表示當前所有可能的 \(f_{j, r}\) 的和，其中 \(j\) 位于滑動(dòng)窗口中，當 \(i\) 增加時(shí)，刪除 \(f_{i, r}\) 并將 \(f_{j, r}\) 加入滑動(dòng)窗口 \(w\)。