首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

POJ 1699 Best Sequence:DFS + 狀態壓縮 DP 求最短超級串

     編輯:C++ 入門

題目大意

給定 n(n ≤ 12)個字串,求包含所有字串作為子串的最短字串長度。允許字串重疊。若一字串已被另一字串包含,可直接刪除。

核心思路:狀態壓縮 DP + DFS

狀態 dp[mask][last] 表示已選字串集合為 mask,最後一個選的是 last 時的最短長度。但本題作者採用預處理重疊增量 + DFS 搜索子狀態的方法。

預處理:計算重疊增量

add[i][j] = 將字串 j 接在字串 i 後面所需增加的長度。即 len[j] - overlap(i, j),其中 overlap 為 i 後綴與 j 前綴的最長匹配長度。

DFS 搜索 + 子狀態枚舉

用整數 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<

關鍵技巧總結

  1. 刪除包含關係:預處理刪除被其他字串包含的字串,減少 n。
  2. 狀態壓縮:n ≤ 12/20 適合 int bitmask。
  3. 子狀態枚舉:for (int sub = (state-1) & state; sub; sub = (sub-1) & state) 高效枚舉所有真子集。
  4. 記憶化搜索:fc[state] 存儲狀態 state(剩餘未選集合)的最優答案。
  5. 重疊預計算:add[i][j] 使轉移 O(1)。

複雜度

  • 狀態數:O(2^n)
  • 每狀態枚舉子狀態:O(2^k)(k 為剩餘數),總體 O(3^n),n≤12 可接受。
  • 作者提到理論值 7kw 操作,實測 AC。

注意

原文代碼有殘缺(HTML 實體轉義導致),核心邏輯為「預處理重疊增量 + 狀態壓縮 DFS + 子狀態枚舉 + 記憶化」。完整正確實現需補全狀態定義、轉移邏輯與邊界處理。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved