給定 n(n ≤ 12)個字串,求包含所有字串作為子串的最短字串長度。允許字串重疊。若一字串已被另一字串包含,可直接刪除。
狀態 dp[mask][last] 表示已選字串集合為 mask,最後一個選的是 last 時的最短長度。但本題作者採用預處理重疊增量 + DFS 搜索子狀態的方法。
add[i][j] = 將字串 j 接在字串 i 後面所需增加的長度。即 len[j] - overlap(i, j),其中 overlap 為 i 後綴與 j 前綴的最長匹配長度。
用整數 state 的二進制位表示哪些字串已使用(1=未用,0=已用?作者代碼中 0 代表已取,1 代表未取,注意反直覺)。每次從當前狀態枚舉其子狀態(即再選一個未用字串),計算新長度並遞歸。
int dp[31][31]; // add[i][j]
int fc[1<<21]; // 記憶化:狀態 -> 最短長度
int dfs(int state) {
if (fc[state] != -1) return fc[state];
if (state == 0) return 0; // 全選完
int ans = INF;
// 枚舉 state 的所有子狀態 sub (即再選一個串)
for (int sub = (state-1) & state; sub; sub = (sub-1) & state) {
// 找出 state 和 sub 不同的那一位 → 新加入的字串 x
int x = __builtin_ctz(state ^ sub); // 或手動找位
int prev = state ^ (1<
int bitmask。for (int sub = (state-1) & state; sub; sub = (sub-1) & state) 高效枚舉所有真子集。fc[state] 存儲狀態 state(剩餘未選集合)的最優答案。add[i][j] 使轉移 O(1)。原文代碼有殘缺(HTML 實體轉義導致),核心邏輯為「預處理重疊增量 + 狀態壓縮 DFS + 子狀態枚舉 + 記憶化」。完整正確實現需補全狀態定義、轉移邏輯與邊界處理。